首页 > 题解 > bzoj 2844 albus就是要第一个出场

bzoj 2844 albus就是要第一个出场

Description

已知一个长度为n的正整数序列A(下标从1开始), 令 S = { x | 1 <= x <= n }, S 的幂集2^S定义为S 所有子集构成的集合。定义映射 f : 2^S -> Zf(空集) = 0f(T) = XOR A[t] , 对于一切t属于T现在albus把2^S中每个集合的f值计算出来, 从小到大排成一行, 记为序列B(下标从1开始)。 给定一个数, 那么这个数在序列B中第1次出现时的下标是多少呢?

Input

第一行一个数n, 为序列A的长度。接下来一行n个数, 为序列A, 用空格隔开。最后一个数Q, 为给定的数.

Output

共一行, 一个整数, 为Q在序列B中第一次出现时的下标模10086的值.

Sample Input

3
1 2 3
1

Sample Output

3

题解

给定n个数以及一个数k,将这n个数的所有子集的异或值从小到大排序得到序列S,求出k在序列S中第一次出现的下标,答案对10086取膜(默认k一定存在)

要解决两个问题:S序列去重之后,k在S中是第几个和S序列中每个数字出现多少次

第一个问题就是把数放到线性基里面插入,每次和线性基里面的数异或的时候就把这位二进制位加到结果里。就是对第k小的查询操作反过来。

对于第二个,定理:B数列中每个数字出现次数都是$2^{(n-cnt)}$。其中cnt是线性基的大小

有了这个定理问题2其实就解决了,这样原问题答案就是$ans*2^{(n-cnt)}+1$,一个快速幂就可以解决

证明也很显然,线性基有个性质:线性基内任意子集异或结果唯一,所有数异或0还是本身,所以每个数字出现的个数就等于(1*异或值为0的集合个数) = 2^(n-cnt)


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×