第一次写线性基，借鉴了PoPoQQQ大神的程序
所以主要做法就不说了，就说一说后面$ans$到底具体是什么
因为我们求线性基是从大到小求所以数字会递减
首先我们像数位dp一样从大到小枚举now,确认一次最多能取多少
因为如果第$i$个数可以取，那么后面的所有线性基都可以在不取当前值的情况下一次取完，所以总共的取法数$ans+=Qpow(2,n-i)$
如果曾经取过一些线性基，那么总取法要加上1(因为之前统计的是绝对<Q的，所以要加上当前的一个)
然后我们得知还有m个自由基，也就是可以经过某些排列组合后进行抵消(等于没用)
所以我们直接确定每个数是否取就行了，所以总共的取法数$ans*=Qpow(2,m)$
最后加上1是因为0也是一种方案
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005,P=10086;
int n,a[N],Q,m,ans;
inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
inline void Gauss(){
int t=0,r;
for(register int i=1<<30;i;i>>=1){
for(register int j=t+1;(r=j)<=n;j++)if(a[j]&i)break;
if(r==n+1)continue;
swap(a[r],a[++t]);
for(register int j=1;j<=n;j++)if(j!=t && (a[j]&i))a[j]^=a[t];
}
m=n-t;
n=t;
}
inline int Qpow(int x,int y){
int z=1;
while(y){
if(y&1)z=z*x%P;
x=x*x%P;
y>>=1;
}
return z;
}
int main(){
freopen("2844.in","r",stdin);
freopen("2844.out","w",stdout);
Read(n);
for(register int i=1;i<=n;i++)Read(a[i]);
Gauss();
Read(Q);
int nw=0;
for(register int i=1;i<=n;i++){
if((nw^a[i])<Q)nw^=a[i],ans=(ans+Qpow(2,n-i))%P;
}
if(Q)ans++;
ans=ans*Qpow(2,m)%P+1;
printf("%d\n",ans%P);
return 0;
}
评论 (0)
