題目大意：給定一個n個數的集合S和一個數x,求x在S的2^n個子集從大到小的異或和序列中最早出現的位置
有學長真好不用自己打題目大意了233
首先我們求出線性基 我們會得到一些從大到小排列的數和一堆0 記錄0的個數
不考慮0，看前面的數，由於線性基的性質，我們直接貪心從大到小枚舉 若當前異或和異或這個值小於Q則取這個數 (注意^不要寫成+或者| 本蒟蒻已經因為這個WA了兩道題了
然後我們通過每個數取不取可以得到一個01序列 這個序列就是通過異或可以得到的小於Q的數的數量的二進制
比如線性基是8 4 2 Q=13 取完8和4之後無法法取2 那麼得到的01序列就是110 即6
然後我們再加上空集的0
然後考慮後面的0 設有m個0 那麼每個數出現的次數為2^m 乘起來後+1就是答案
一個細節就是當Q=0的時候計算小於Q的數的數量時不要算上0 不懂的可以自己測測0
#include#include #include #include #define M 100100 #define Mo 10086 using namespace std; int n,m,q,ans,a[M]; void Gaussian_Elimination() { int i,j,k=0; for(j=1<<30;j;j>>=1) { for(i=k+1;i<=n;i++) if(a[i]&j) break; if(i==n+1) continue; swap(a[i],a[++k]); for(i=1;i<=n;i++) if(i!=k) if(a[i]&j) a[i]^=a[k]; } m=n-k; n=k; } int ksm(int x,int y) { int re=1; while(y) { if(y&1)re*=x,re%=Mo; x*=x,x%=Mo; y>>=1; } return re; } int main() { int i,num,now=0; cin>>n; for(i=1;i<=n;i++) scanf("%d",&a[i]); Gaussian_Elimination(); cin>>q; for(i=1;i<=n;i++) if( (now^a[i])
