洛谷P4869 albus就是要第一个出场（线性基）

不知道线性基是什么东西的可以看看蒟蒻的总结

线性基居然有这性质我还不知道orz

假设$n$个数的线性基中有$k$个数，那么显然共有$2^k$个不同的异或和，而其中每一个异或和的出现次数都是$2^{n-k}$

感性理解一下的话……就是不在线性基中的每一个数字都可以被线性基中的数字表示出来从而异或之后为0，那么这些数字都可以看做0,

所以每一个异或和都可以异或上0变成自己，那么0有多少种选法呢？加上空集就是$2^{n-k}$种

然后只要算出$q$之前有多少个数就好了……

然后这个东西具体怎么算……看代码好了……

 //minamoto

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while((ch=getc())>''||ch<'')

     (ch=='-')&&(flag=true);

     for(res=num;(ch=getc())<=''&&ch>='';res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int mod=;

 int b[],st[],top,n,q,rk;

 inline int ksm(int x,int y){

     int res=;

     while(y){

         if(y&) (res*=x)%=mod;

         (x*=x)%=mod,y>>=;

     }

     return res;

 }

 void insert(int x){

     for(int i=;i>=;--i)

     if(x>>i&){

         if(!b[i]) return (void)(b[i]=x);

         x^=b[i];

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read();

     for(int i=,x;i<=n;++i) insert(x=read());

     q=read();

     for(int i=;i<=;++i)

     if(b[i]) st[top++]=i;

     for(int i=;i<top;++i)

     if(q>>st[i]&) rk+=<<i;

     printf("%d\n",(1ll*rk*ksm(,n-top)+)%mod);

     return ;

 }

巴特西

洛谷P4869 albus就是要第一个出场（线性基）

最新文章

热门文章