这题还是有点新意的,套路部分就不讲了,我们套路前缀和,然后就知道要用一个trie树这样的东西来维护一下,如果有人这里不是
很熟可以看一下我之前写的https://blog.nowcoder.net/n/744869ac01154d47b1240cfaebc3839e
接着我们来看一下如何处理,我们有点像是在trie上统计若干的子树的sz和,这样的一个二分的过程
我们来看具体维护,我们考虑当前是在第k位,然后当前val的第k位是x,K的第k为是y
那么如果y是0
那么我们相当于对于xor val的这一位就有两种选择
其中如果异或出来是1的那种选法我们无论底下怎么选都是满足条件的
反之我们就必须只有一种选法。
具体可以看代码,然后我们还需要加上最后到达的节点的sz,这个是刚好等于K的个数。
代码:
#include<bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x<<" = "<<x #define sp <<" " #define el <<endl #define fgx cerr<<" ------------------------------------------------ "<<endl #define LL long long #define DB double #define mpt make_pair #define pb push_back inline int read(){ int nm=0; bool fh=true; char cw=getchar(); for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-'); for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0'); return fh?nm:-nm; } #define M 1000200 int n,K,tot,all; LL ans; int sz[M<<5],ch[M<<5][2]; inline void ins(){ int nw=1; for(int k=30,t;~k;--k){ t=(all&(1<<k))>0; if(!ch[nw][t]) ch[nw][t]=++tot; nw=ch[nw][t],++sz[nw]; } } int main(){ n=read(),K=read(),tot=1,ins(); for(int i=1,x;i<=n;i++){ x=read(),all^=x; int nw=1; for(int k=30,t,tk;~k;--k){ t=(all&(1<<k))>0,tk=(K&(1<<k))>0; if(!tk) ans+=(LL)sz[ch[nw][t^1]]; nw=ch[nw][t^tk]; } ans+=(LL)sz[nw],ins(); //debug(i)sp,debug(ans)el; } printf("%lld\n",ans); return 0; }