非常有助于理解线性基的一题。
构造线性基$B$后，如果$|A| > |B|$，那么就意味着有些数可以由$B$中的数异或出来，而多的数可以取或者不取，相当于每多一个数，那么线性基能生成的数的子集的种类就可以乘以$2$，最终就是乘以$2^{|A|-|B|}$。
所以对于给定的$Q$，要确定它是由哪些位置的线性基中的数生成的，然后确定它在不重复序列中的位置，然后再乘以$2^{|A|-|B|}$，最终还需要$+1$，因为前面求的其实是不包含这个数的子集总个数。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 #define ll long long 5 #define Min(a,b) ((a)>(b)?(b):(a)) 6 #define Max(a,b) ((a)>(b)?(a):(b)) 7 const int MAXN = 1e5 + 13; 8 const int MAXL = 30; 9 const int mod = 10086; 10 int base[MAXL + 2]; 11 12 int Pow(int a, int b) 13 { 14 int ans = 1; 15 while(b) { 16 if(b & 1) ans = ans * a % mod; 17 b >>= 1; 18 a = a * a % mod; 19 } 20 return ans; 21 } 22 23 24 int main() 25 { 26 //freopen("input.txt", "r", stdin); 27 //freopen("out.txt", "w", stdout); 28 int n, a, cnt = 0, q; 29 scanf("%d", &n); 30 memset(base, 0, sizeof(base)); 31 for(int i = 0; i < n; i++) { 32 scanf("%d", &a); 33 for(int j = MAXL; j >= 0; j--) { 34 if(a & (1<<j)) { 35 if(base[j]) 36 a ^= base[j]; 37 else { 38 base[j] = a; 39 for(int k = j - 1; k >= 0; k--) { 40 if(base[j] & (1<<k) ) 41 base[j] ^= base[k]; 42 } 43 for(int k = j + 1; k <= MAXL; k++) { 44 if(base[k] & (1<<j) ) 45 base[k] ^= base[j]; 46 } 47 cnt++; 48 break; 49 } 50 } 51 } 52 } 53 scanf("%d", &q); 54 vector<int> pos; 55 int p = 0, res = 0; 56 for(int i = 0; i <= MAXL; i++) { 57 if(base[i]) pos.push_back(i); 58 } 59 for(int i = 0; i < pos.size(); i++) { 60 if(q>>pos[i] & 1) { 61 res += (1<<i); 62 } 63 } 64 printf("%d\n", (res % mod * Pow(2, n - cnt) % mod + 1)%mod ); 65 return 0; 66 }
原文：https://www.cnblogs.com/dybala21/p/11366783.html