爱华网
感觉XOR高斯消元是个挺有意思的东西.
我又调了很久，纪念一下.
（顺便吐槽，最近如此糟糕的状态，高仿都会WA啊）
先讲下 HDU 3949 XOR http://acm.hdu.edu.cn/showproblem.php?pid=3949
题意是这样的.
给出A数组，共有N个数，你可以选其中一些出来XOR（至少一个数）.
所以可能的XOR结果值排序后去重，问你排在第k个的结果值是多少.
解法是这样的:
定义数组的矩阵为，我们把数组中每个数用二进制表示出来的矩阵.（N行64列）.
数组的集合为，数组所有可能取出任意大于一个数，互相XOR的结果值.
我们用原来A数组的N个数，类似高斯消元互相XOR成，新的A'数组.且A'具有以下性质:
1将A'从大到小排序,那么子数组A[i..n]的集合中的最大值<A[i-1]<A[i-2]..<A[1]
2A数组的集合<->A'数组的集合
具体怎么构造，先贴段代码:
#define rep(i,n) for (inti=1;i<=n;i++)#define rep2(i,l,r) for (inti=l;i<=r;i++)int Gauss(){ int m=31,cu=1; while (m--){ rep2(i,cu,n) if(a[i]>>m&1){ swap(a[i],a[cu]); rep(j,n)if(j!=cu&&a[j]>>m&1)a[j]^=a[cu]; cu++; break; } } return --cu;}解释一下 为什么这样做+具体怎么做.首先，这是在数组的矩阵中做的.
定义，每行（数）的第一个（最高位）出现的1，为这行的代表.
如果A'的每行的代表，在数组的矩阵中的所在列，只有它这行有1(3). 显然就可以满足性质1了.【最高位决定一切，比它小的必没有最高位，那么怎么也不会XOR不出最高位】
又为了在已知A'数组的集合包含于A数组的集合的情况下【A'是由A xor来的，且x被xor多次最多只会保留一个】，尽量满足性质2. 即A'能互相xor的可能结果值要尽量多，即每行有尽量少的1【够自由，方便构造】(4).
为此. 我们从高到低位，尝试在这列中“授予"代表.
设当前第m位，为了(4)，我们去找第m位有1且还没有代表的行.为了方便，程序中，没有代表的行是连续的，且为cu-n行.假设找到满足条件的第i行，把第i行变为有代表且代表为m.为了保持没有代表行连续的性质，我们将i与cu互换，cu+1.
由于m位为代表出现在cu行，那么其他所有m位为1的a[j]^=a[i].从而保证了(3).
会不会冲掉原来的代表呢？由于a[cu]的那些位已经被消成0了，所以显然不会.
然后就OK了.先再说两个可能存在的误区：
1 矩阵中任意一列只有一个1. 这是错误的，反例如A={5,3} .
2 矩阵中任意一行只有一个1.这也是错误的，反例如A={3}.
其实性质一不需要这两个约束就可以满足.
鉴于性质1已经显然满足了，再说明一下为什么满足性质2.
假如，现在给第cu行授予位于第m位的代表.然后为了满足性质1大家xor了一下.
如果我们能够说明，这一步xor前与xor后所能互相xor的结果值的集合相同，那么一直推到最前面的初始序列，就可以说明满足性质2了.
xor前的可以分成三类 1)W={ Xcu 1 Ycu} 2)Q={Xi 1 Yi} 3)P={Xj 0Yj}
解释一下.Xz表示z行第m位前面的部分，Yz表示z行第m位后面的部分. 然后第一类就是cu行自己.第二类是所有第m位为1的集合，第三类是所有第m位为0的集合. (那么|W|+|Q|+|P|=n，Az=Xz1Yz)
经过这一步的xor后会变成:W'={Xcu 1 Ycu} Q'={(Xi 1 Yi)xor Acu}P'={Xj 0Yj}.
代表是从高到低位找的，且代表单独一列.所以显然有 Xcu=000..0 .Q'即={(Xi 1 (Yi xorAcu)}
显然 xor后的集合包含于xor前的集合【和前面A'属于A一个道理】.所以只需说明，任意一个xor前能产生的异或和，都能在xor后找到对应（即xor前的集合属于 xor后的集合）
对于某个异或和S，分成三类分别放一起后可以表示成S=wxor q xor p.
其中w为W中的那些放一起异或，q,p同理. 并且，由于有空集的存在w,q,p 都可以为0.
由于P=P'，所以p肯定能在P'中构造出对于w,q，如果我们找到Q'中对应的，那些本来在Q中找到用来构造q的，异或起来.显然只有两种情况，得到 q'=q 或者 q'=q xor Acu.w'便可根据此调节：
若q'=q,w=0 或者 q'=q xor Acu,w=Acu.. w'=0 ；若q'=q,w=Acu 或者 q'=q xor Acu,w=0..w'=Acu.
所以就感性的说明了性质2满足.由于我表达能力有限，不懂的话，就自己试试以上的以步骤来数学归纳的证明方法吧. 还是比较容易的..
好了，构造好A'，那么就很方便了：把B数组排序，再把k二进制分解.找对应有1的XOR起来就好了.
举个例子 A'={8,5,2}找第3(011(2))个 ，就是 5 xor2.而找第5(101(2))个就是 8xor2.
有了A'的两个性质. 正确性还是比较显然的.当然，在性质2的基础上，性质1也很重要！
还要提到的是，HDU这题对于0要特判【由于至少要取1个】然后对于BZOJP2844这题是反一下.由于有误区1，显然不能直接((k^A'[i])==A'[i])这样判，而是尝试xor，看看是否还比k小，小的话就xor加入.【具体看程序】但是，会不会出现某行多余的1，最终会被消掉，但是当前却因此大于了k了呢？显然不会.首先由于代表是从高到低一个个尝试找的，所以所有代表的位数，一定高于非代表（多余的1）的位.如果这个多余的1会被消掉，那么必然至少还有一个代表没加入，而代表是单独一列只有自己一个1的.即那个代表没加入，则k的那个代表这一位必然为1，且当前必然为0.这个位高于那个多余的1所在位，所以就没事啦..
但是要注意，由于这里不去重，如果消完后有Q行至少有1个1,其他N-Q行全为0.那么任意一个结果值出现 2^(N-Q)次. 所以要乘上什么的，详见程序吧. 然后就好了 恩.
code:#include<cstdio>
#include< cstdlib>
#include< cstring>
#include< algorithm>
using namespace std;
typedef unsigned long long ll;
const ll mo=10086;
int n,a[100005],Q;
#define rep(i,n) for (int i=1;i<=n;i++)
#define rep2(i,l,r) for (int i=l;i<=r;i++)
void swap(int &a,int &b){ intt=a;a=b;b=t; }
int Gauss(){
intm=31,cu=1;
while(m--){
rep2(i,cu,n) if(a[i]>>m&1){
swap(a[i],a[cu]);
rep(j,n) if(j!=cu&&a[j]>>m&1)a[j]^=a[cu];
cu++;break;
}
}
return--cu;
}
int main(){
scanf("%d",&n);
rep(i,n)scanf("%d",&a[i]);
scanf("%d",&Q);
intva=Gauss(),cu=0; ll rk=0;
rep(i,va) if((cu^a[i])<=Q)cu^=a[i],rk+=(1ll<<(va-i))%mo,rk%=mo;
rep(i,n-va)rk<<=1,rk%=mo; rk++,rk%=mo;
printf("%llun",rk);
return0;
}
