题目链接：https://ac.nowcoder.com/acm/contest/881/H
题目大意：给定n个整数，求满足子集异或和为0的子集大小之和。
解题报告：
先把n个数分成两部分，线性基外与线性基内
1. 对n个数试着插入线性基，如果不能插入，证明它能被线性基内的数异或得到，即这个数的贡献为1，把这些不能插入线性基的数构成一个集合，考虑一个数必选，那么与它组合的方式共有$2^{n-r-1}$种，r为线性基内的数，减1是为了减去这个数（因为它必选），共有$（n-r）$个数，所以线性基外的数的贡献为$(n-r)*2^{n-r-1}$
2. 对于线性基内的数，枚举每一个数，对于剩下的n-1个数建立线性基，如果它不能插入线性基，不难证明这个线性基的大小已经为r，这个数的贡献便为1，总共有temp个数，所以线性基内的数的总贡献便为$temp*2^{n-r-1}$
答案：$(n-r)*2^{n-r-1}+temp*2^{n-r-1}$
AC代码：
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(' ') 4 #define pn putchar(' ') 5 #define pb push_back 6 #define fi first 7 #define se second 8 #define fre1 freopen("1.txt","r",stdin) 9 #define fre2 freopen("2.txt","w",stdout) 10 using namespace std; 11 template <typename T> 12 void read(T &res) { 13 bool flag=false;char ch; 14 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 15 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 16 flag&&(res=-res); 17 } 18 template <typename T> 19 void write(T x) { 20 if(x<0) putchar('-'),x=-x; 21 if(x>9) write(x/10); 22 putchar(x%10+'0'); 23 } 24 typedef long long ll; 25 const int maxn=1e5+7; 26 const int N=60; 27 const ll mod=1e9+7; 28 struct node { 29 int r; 30 ll p[70]; 31 void init() { 32 r=0; 33 for(int i=62;~i;i--) 34 p[i]=0; 35 } 36 bool ins(ll x) { 37 for(ll i=62;~i;i--) { 38 if(x&(1LL<<i)){ 39 if(!p[i]) { 40 p[i]=x; 41 r++; 42 return true; 43 } else x^=p[i]; 44 } 45 } 46 return false; 47 } 48 }b1,b2,b3; 49 vector<ll>v; 50 ll quickpow(ll a,ll b) { 51 ll ans=1; 52 while(b) { 53 if(b&1) ans=(ans*a)%mod; 54 a=(a*a)%mod; 55 b>>=1; 56 } 57 return ans; 58 } 59 int main() 60 { 61 int n; 62 while(scanf("%d",&n)!=EOF) { 63 b1.init(); 64 b2.init(); 65 b3.init(); 66 v.clear(); 67 for(int i=1;i<=n;i++) { 68 ll x; 69 read(x); 70 if(b1.ins(x)) { ///线性基内 71 v.pb(x); 72 } 73 else b2.ins(x); ///线性基外 74 } 75 if(b1.r==n) { 76 write(0);pn;continue; 77 } 78 ll ans=(n-b1.r)*quickpow(2,n-b1.r-1)%mod;///线性基外求解 79 ll temp=0; 80 for(int i=0;i<v.size();i++) { ///线性基内求解 81 b3=b2; 82 for(int j=0;j<v.size();j++) { 83 if(i==j) continue; 84 b3.ins(v[j]); 85 } 86 if(b3.r==b1.r) temp++; 87 } 88 ans=(ans+temp*quickpow(2,n-b1.r-1))%mod; 89 write(ans);pn; 90 } 91 return 0; 92 }