给定n个整数，将数分解成01序列，由这n个01序列构成矩阵，这n个数构成线性空间，这就是异或空间
将这个矩阵高斯消元，求出t个主元，那么由着t个主元构成的线性空间里总共有2^t个数
设这t个数分别是a1,a2,a3,a4,...at，每个数代表的主元为二进制上的一位1，显然选a1的情况组成的数，必定比不选a1的情况组成的数要大
比如a1...a5转换成二进制后将主元取出来就是 1 1 1 1 1
那么异或空间中，（为了对应整齐，将第1小的数改为第0小，依次类推）
最小(0)的数就是 0 0 0 0 0即一个也不取，
第二(1)小的数就是0 0 0 0 1，即只取a5的情况
第三(2)小的数就是0 0 0 1 0，即只取a4的情况
第四(3)小的数就是 0 0 0 1 1，即取a4，a5的情况
显而易见 ，第k大的数对应的取法就是k的二进制表示中为1的位！
那么异或空间中最大数（2^t-1）显然是所有数的异或（把每一位都异或为1的情况），最小数(0)就是一个也不取的情况（0）
那么第k大的数就是将k-1 (把k-1为了方便从最小的数开始算起)进行二进制分解，然后取出对应的ai进行异或即可
但是本题中可能存在最小的数（0）不存在的情况：因为不允许xi ^ xi的情况
所以如果给定的数组a不能异或出0的值，就把k-1再加1即可，反之就用k-1进行二进制分解
如何判断能否异或出0的情况？高斯消元后是否有0行出现，即矩阵的秩小于矩阵的行数
普通的高斯消元复杂度数O（n3），其中一个n是矩阵的秩，一个n是矩阵行数，一个n是列数
那么异或空间的复杂度就是O(63*63*n)，一个63为秩，一个63为列数，n为行数
但实际上复杂度为O(63*n)，因为异或运算可以把消元的复杂度从m改为1，即对于每行来说只要异或一次就行了
此外，求异或矩阵的主元时，要把除了主元位的其它位都清零，我自己做的时候由于没有清零主元两侧的位，wa了好多发，最后和网上的一对比
发现必须要清楚主元两侧的位
#include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 100005 int t,n,q,rk; ll k; ll A[maxn],B[maxn],P[maxn]; void Gauss(int n) { memset(P,0,sizeof(P)); for (int i=1;i<=n;i++) { for (int j=63;j>=0;j--) { if ((A[i]>>j)&1) { if (P[j]) A[i]^=P[j];//把这一列的清了 else {P[j]=A[i]; break;}//这行第j个作为主元，因为到第j位就退出了，所以后面的之后再清零 } } } for (int i=63;i>=0;i--)//把P[i]除了主元位的1之外的位（在主元右侧的1）清了 { if (!P[i]) continue; for (int j=i+1;j<=62;j++) { if ((P[j]>>i)&1) P[j]^=P[i]; } } rk=0; for (int j=0;j<=63;j++) if (P[j]) P[rk++]=P[j]; } /*void Gauss(){ memset(P,0,sizeof P); for(int i=1;i<=n;i++) for(int j=63;j>=0;j--) if((A[i]>>j) & 1){//判断A[i][j]==1 if(P[j]==0){P[j]=i;break;} //A[i][j]设为主元 else A[i]^=A[P[j]];//用其他主元把A[i][j]变成0 } for(int i=63;i>=0;i--){ if(!A[P[i]])continue; for(int j=i+1;j<=62;j++) if((A[P[j]]>>i)&1)A[P[j]]^=A[P[i]]; } rk=0; for(int j=0;j<=63;j++)//简化后的矩阵B,B[0]为at if(A[P[j]])B[rk++]=A[P[j]]; }*/ int main(){ cin>>t; for(int tt=1;tt<=t;tt++){ printf("Case #%d:\n",tt); cin>>n; for(int i=1;i<=n;i++)cin>>A[i]; Gauss(n);//预处理构建矩阵 cin>>q; while(q--){ cin>>k; if(n!=rk)k--;//不能异或出0 if(k>=(1ll<<rk))puts("-1"); else { ll ans=0; for(int j=0;j<=63;j++)//测试k的二进制位 if((k>>j)&1) ans^=P[j]; cout<<ans<<endl; } } } }
转载于:https://www.cnblogs.com/zsben991126/p/10533963.html
相关资源：各显卡算力对照表！