【题目分析】
高斯消元求线性基。
题目本身不难，但是两种维护线性基的方法引起了我的思考。
void gauss(){
k=n;
F(i,1,n){
F(j,i+1,n) if (a[j]>a[i]) swap(a[i],a[j]);
if (!a[i]) {k=i-1; break;}
D(j,30,0) if (a[i]>>j & 1){
b[i]=j;
F(x,1,n) if (x!=i && a[x]>>j&1) a[x]^=a[i];
break;
}
}
}
——高斯消元求线性基
for (int i=1;i<=n;++i)
for (int j=31;j>=0;--j)
if ((a[i]>>j)&1){
if (!lb[j]) {lb[j]=a[i]; cnt++; break;}
else a[i]^=lb[j];
}
——动态维护线性基
不会高斯消元解Xor方程组的我，直接使用了第二种方式求解，发现直接WA飞了。
（后来一想，居然过了样例）。
那么他们有什么差别呢。
我对拍了许多组，发现他们求出的线性基的大小是相同的。
但是高斯消元的线性基有一个神奇的特征，是使得该位为1的最小的数。（最小的）
那么有必要去写高斯消元吗？
显然不必要，做一个小操作就好了。
于是改了改动态维护线性基的代码，成了这个样子 ↓
for (int i=1;i<=n;++i)
for (int j=31;j>=0;--j)
if ((a[i]>>j)&1){
if (!lb[j]) {lb[j]=a[i]; cnt++; break;}
else a[i]^=lb[j];
}
for (int i=31;i>=0;--i)
if (lb[i])
for (int j=i-1;j>=0;--j)
if ((lb[i]>>j)&1) lb[i]^=lb[j];
——改版
神奇的AC了。线性基与高斯消元的结果相同。
考虑时间复杂度，都是log*n的，自然没什么差别，但是用哪种就是仁者见仁智者见智了。
实际上高斯消元会快一些（达不到复杂度上限），而动态维护线性基是标准的上限（雾）
【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define maxn 100005
#define ll long long
int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const int mod=10086;
int n,cnt=0,q;
int lb[34],a[maxn];
int power(int a,int b)
{
// printf ("Pow %d ^ %d is ",a,b);
int ret=1;
while (b)
{
if (b&1) (ret*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
// printf("%d\n",ret);
return ret;
}
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
n=read();
for (int i=1;i<=n;++i) a[i]=read();
// sort(a+1,a+n+1);
// for (int i=1;i<=n;++i) cout<<a[i]<<" "; cout<<endl;
q=read();
// cout<<"query : "<<q<<endl;
for (int i=1;i<=n;++i)
for (int j=31;j>=0;--j)
if ((a[i]>>j)&1){
if (!lb[j]) {lb[j]=a[i]; cnt++; break;}
else a[i]^=lb[j];
}
for (int i=31;i>=0;--i)
if (lb[i])
for (int j=i-1;j>=0;--j)
if ((lb[i]>>j)&1) lb[i]^=lb[j];
// printf("The Xor Base is %d\n",cnt);
int rk=0,x=0,tmp=0;
for (int j=31;j>=0;--j)
if (lb[j]){
tmp++;
// cout<<tmp<<":"<<lb[j]<<endl;
if ((x^lb[j])>q) continue;
x^=lb[j];
// printf("now add %d\n",cnt-tmp);
rk=(rk+power(2,cnt-tmp))%mod;
}
for (int i=1;i<=n-cnt;++i)
rk=(rk*2)%mod;
rk++;
cout<<rk<<endl;
}