【HDU 3949】 XOR （线性基，高斯消元）

 

【题意】

　　给n个数，可以在其中选任意个数异或，求所有异或出来的答案中的第k个。

 

【分析】

　　

　　求线性基？好像很厉害的东西..
　　证明的话应该要用到X^Y=Z -> X^Z=Y这个性质
　　线性基的相互异或的值可以完全代替原来的n个数的异或的值，这样数从n个变成了二进制位数个，数减少了很多这是一个优点。
　　另外，像高斯消元一样求线性基的话，如果某一位上有代表这一位的1，那么其他位置上一定为0。（这个性质好像很好用，因为这样可以看作这个数是对这一位作唯一贡献的，这样求很多东西都很方便了） 所以感觉异或版的高斯消元跟普通的高斯消还是很不一样的，多了好性质啊..

　　放一下让我看懂的解释吧~

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 10010

 #define LL long long

 LL a[Maxn],num[];

 int n,cnt;

 void gauss()

 {

     int l=,r=;

     LL t;

     while(l<=n&&r>=)

     {

         if(!(a[l]&(1LL<<r-)))

         {

             for(int i=l+;i<=n;i++) if(a[i]&(1LL<<r-))

             {

                 t=a[l],a[l]=a[i],a[i]=t;

                 break;

             }

         }

         if(!(a[l]&(1LL<<r-)))

         {

             r--;continue;

         }

         num[r]=l;

         for(int i=;i<=n;i++) if(i!=l&&(a[i]&(1LL<<r-))) a[i]^=a[l];

         l++;r--;

     }

 }

 void init()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     memset(num,,sizeof(num));

     gauss();

     for(int i=;i<=;i++) if(num[i]!=) num[i]=a[num[i]];

     cnt=;

     for(int i=;i<=;i++) if(num[i]!=) cnt++;

 }

 int main()

 {

     int T,kase=;

     scanf("%d",&T);

     while(T--)

     {

         init();

         printf("Case #%d:\n",++kase);

         int q;

         scanf("%d",&q);

         while(q--)

         {

             LL k;

             scanf("%lld",&k);

             if(cnt==n) k++;//zero

             if(k>(1LL<<cnt)) {printf("-1\n");continue;}

             int now=cnt;

             LL ans=;

             for(int i=;i>=;i--) if(num[i]!=)

             {

                 LL x=(1LL<<now-);

                 if(k>x) ans^=num[i],k-=x;

                 now--;

             }

             printf("%lld\n",ans);

         }

     }

     return ;

 }

[HDU3969]

2016-09-30 15:03:05