做法: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;
}