做法:01Trie
思路
我们可以先求异或前缀和
然后套上字典树
在执行find时
如果 k 的这一位是 1 ,那么必须往 1 那一边走。
如果 k 的这一位是 0 ,那么分情况讨论
如果往 1 走,那么整个子树内所有的叶子结点都要计算。
如果往 0 走,那么继续循环下去
最后不要忘记等于k的个数
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=1000010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); int n,k,a[N],s[N]; ll ans; struct Trie { int nex[N*32][2],cnt=1; ll siz[N*32]; void insert(int x) { int p = 1; for (int i = 30; i >= 0; i--) { int c = x>>i&1; if (!nex[p][c]) nex[p][c] = ++cnt; p = nex[p][c]; siz[p]++; } } ll find(int x) { int p =1; ll res = 0; for (int i = 30; i >= 0; i--) { int c = x>>i&1; if(k>>i&1) p=nex[p][c^1]; else res+=siz[nex[p][c^1]],p=nex[p][c]; } res+=siz[p]; return res; } } t; void solve(){ cin>>n>>k; rep(i,1,n){ cin>>a[i]; s[i]=s[i-1]^a[i]; } rep(i,1,n){ t.insert(s[i-1]); ans+=t.find(s[i]); } cout<<ans<<'\n'; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }