高斯消元解XOR方程组

 1 /************************************************************** 2     Problem: 2844 3     User: Tunix 4     Language: C++ 5     Result: Accepted 6     Time:252 ms 7     Memory:2052 kb 8 ****************************************************************/ 9  10 //BZOJ 284411 //srO ZYF Orz12 #include<cstdio>13 #include<cstring>14 #include<cstdlib>15 #include<iostream>16 #include<algorithm>17 #define rep(i,n) for(int i=0;i<n;++i)18 #define F(i,j,n) for(int i=j;i<=n;++i)19 #define D(i,j,n) for(int i=j;i>=n;--i)20 using namespace std;21 void read(int &v){22     v=0; int sign=1; char ch=getchar();23     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();}25     v*=sign;26 }27 /******************tamplate*********************/28 const int N=100010,MOD=10086;29 int n,m,k,a[N],b[N];30 void gauss(){31     k=n;32     F(i,1,n){33         F(j,i+1,n) if (a[j]>a[i]) swap(a[i],a[j]);34         if (!a[i]) {k=i-1; break;}35         D(j,30,0) if (a[i]>>j & 1){36             b[i]=j;37             F(x,1,n) if (x!=i && a[x]>>j&1) a[x]^=a[i];38             break;39         }40     }41 }42 inline int pow(int x,int y){43     int t=1;44     for(;y;y>>=1,x=x*x%MOD)45         if (y&1) t=t*x%MOD;46     return t;47 }48  49 int main(){50     read(n);51     F(i,1,n) read(a[i]);52     read(m);53     gauss();54     int ans=1;55     F(i,1,k) if (m>>b[i]&1){56         m^=a[i];57         ans=(ans+pow(2,n-i))%MOD;58     }59     printf("%d\n",ans);60     return 0;61 }62