Bitwise Xor-题解
starseven
2020-06-13 12:38:52
[CF通道](https://codeforces.com/gym/102331/problem/B)
[luogu通道](https://www.cnblogs.com/starseven/p/13113915.html)
[我的博文通道](https://www.cnblogs.com/starseven/p/13113915.html)
------------
# 题意
给你一个$n$长度的序列，叫你求有多少个子序列满足：
这子序列中任意两个数取反的值≥X
# 输入
$n\;\;x$
$a_1\;a_2\;a_3\dots a_n$
# 数据范围
$$ X\leq 2^{60}-1 $$
$$ a_i\leq 2^{60}-1,i\in[1,n] $$
$$ n\leq 3\times 10^5 $$
# 分析
刚拿到这道题时，我心中只有暴力（可是这是CF赛制）
然后就是听老师讲“若干个数两两异或的最小值必在排序后相邻两个取到”。可是我并没法理解（当然，我当时以为是“或”而不是“异或”）。
所以当我知道是异或的时候，我自己脑袋里面已经有了一些思路。
-----------
我们设$x\leq y\leq z$
$⊕$是取反的意思
然后我们可以知道：
1. $(x⊕y)⊕(y⊕z)==z⊕x$
这相当于是将y给抵消了吧。
口头证明：
（~~只可意会不可言传~~）
好吧，这个坑我之后再补，可是应该能够想象出来，但是也可以用代码做下实验
```cpp
int x1,x2,x3;
cin>>x1>>x2>>x3;
int judge1=x1^x2,judge2=x2^x3;
if(x1^x3==judge1^judge2) cout<<"TRUE"<<endl;
else cout<<"False"<<endl;
```
2. $min(x⊕y,y⊕z)\leq x⊕z$
$$\dots\dots$$
我也不会证明，可是代码验证是对的
根据上面的两个式子，我们就可以将这个当成DP来做了
$dp[i]$代表的是选择$a_i$为子序列的末尾，有多少个合法的子序列。
转移方程就是:
$$f[i]=1+\sum_{j=1,f[i]⊕f[j]>=x}^{i-1}f[j]$$
为什么要$+1$呢，因为单独一个数也可以构成合法的子序列（我也不知道为什么）
所以我们就得到了方程。
那怎么统计答案呢？
我们思考，$f[i]$代表的意思是什么？
$f[i]$代表的是i必选，有多少个合法序列。-->这个是根据状态转移得出的。
所以最终答案就是$\sum_{i=1}^{n}f[i]$
而我们得出的方程式的时间复杂度为$O(n^2)$
怎么优化？
根据题意可知道，我们可以使用$trie$优化，具体细节看代码就懂
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ri register int
#define Starseven main
#define ll long long
using namespace std;
const int N=3e5+20;
const ll mod=998244353;
ll a[N],x,f[N],sum[N*60];
int n,ch[N*60][2],cnt=1;//因为起点是从1开始的，所以cnt应该从2开始，初始化为一
void Insert(ll add,ll s){
int u=1;
for(ri i=60;i>=0;i--){
int c=((s>>i)&1);
if(!ch[u][c]) ch[u][c]=++cnt;
u=ch[u][c];sum[u]=(sum[u]+add)%mod;
}
return ;
}
ll Query(ll s){
ll re=0;
int u=1;
for(ri i=60;i>=0;i--){
if((x>>i)&1) u=ch[u][((s>>i)&1)==0];//这里保证了经过的点在XOR过程中始终=x
else{
re=(re+sum[ch[u][((s>>i)&1)==0]])%mod;
u=ch[u][((s>>i)&1)!=0];//理解
}
}
return (re+sum[u])%mod;
}
int Starseven(void){
cin>>n>>x;
for(ri i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(ri i=1;i<=n;i++){
f[i]=(Query(a[i])+1)%mod;
Insert(f[i],a[i]);
}
ll ans=0;
for(ri i=1;i<=n;i++) ans=(ans+f[i])%mod;
cout<<ans<<endl;
return 0;
}
```