Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /***
- created: 2023-02-09-16.52.23
- ***/
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
- #define ll long long
- #define all(we) we.begin(),we.end()
- #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
- #define nl '\n'
- const ll mx=20*100005;
- ll trie1[mx][2];
- ll cnt[mx],sz,k;
- void insert1(ll x)
- {
- ll now=0;
- for(ll i=20; i>=0; i--)
- {
- bool b=(x&(1<<i));
- if(trie1[now][b]==0)
- {
- trie1[now][b]=++sz;
- }
- now=trie1[now][b];
- cnt[now]++;
- }
- }
- ll query(ll x)
- {
- ll ans=0,now=0;
- for(ll i=20; i>=0; i--)
- {
- bool bk=(k & (1<<i));
- bool bx=(x & (1<<i));
- if(bk)
- {
- ans+=cnt[trie1[now][bx]];
- if(trie1[now][(bx^1)]==0) break;
- now=trie1[now][(bx^1)];
- }
- else
- {
- if(trie1[now][bx]==0) break;
- now=trie1[now][bx];
- }
- }
- return ans;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- test
- {
- ll n,m,i,j,l=0,ans=0;
- cin>>n>>k;
- sz=0;
- memset(trie1,0,sizeof trie1);
- memset(cnt,0,sizeof cnt);
- insert1(0);
- for(i=0; i<n; i++)
- {
- cin>>m;
- if(i==0)
- {
- l=m;
- ans+=query(l);
- insert1(l);
- }
- else
- {
- l^=m;
- ans+=query(l);
- insert1(l);
- }
- }
- cout<<ans<<nl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement