Solution
首先可以把 a 排序,显然不影响答案。
事实上,这个子序列的两两异或最小值只可能在排序后相邻两项中取得。
证明: 设 a ≤ b ≤ c,我们只需证明 min{a ⊕ b, b ⊕ c} ≤ a ⊕ c。
当 a = b 或 b = c 时显然,因此不妨设 a < b < c。如果 a, b, c 的某一位都相等,则两两异或的那一位也相等,因此可以忽略这一位。
找到最高 的一位 d 使得 a, b, c 的第 d 位不全相等。 有两种情况:
- 若 a, b, c 的第 d 位分别为 0, 0, 1,则 a ⊕ b ≤ a ⊕ c。
- 若 a, b, c 的第 d 位分别为 0, 1, 1,则 b ⊕ c ≤ a ⊕ c。
无论哪种情况,都有 min{a ⊕ b, b ⊕ c} ≤ a ⊕ c。证毕。(转自gmoj题解)
然后就可以设 f [ i ] 表示为以 a [ i ] 结束的合法子序列个数,n2转移显然。
考虑用 trie 树优化,将 f [ 1~ i-1 ] 挂在节点上再维护子树和,那么怎样求 f [ i ] 呢?
若当前 x 这一位 = 0,那么答案加上上当前节点儿子和 a [ i ] 这一位异或起来 = 1的子树,递归
若当前 x 这一位 = 1,直接递归。
注意 自己成为一个子序列的情况。
Code
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int N=3e5+10,M=65,mo=998244353; int f[N*M],b[M],s[N*M][2]; ll a[N]; int n,i,t,an,rt,p; ll X; int ask(int x,int d,ll y){ if (!x) return 0; if (d<0) return f[x]; int z=y>>d&1; return (f[s[x][z^1]]*(b[d]^1)+ask(s[x][z^b[d]],d-1,y))%mo; } void insert(int &x,int d,ll y){ if (!x) x=++t; f[x]=(f[x]+p)%mo; if (d<0) return; insert(s[x][(y>>d)&1],d-1,y); } int main(){ freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); scanf("%d%lld",&n,&X); for(i=0;i<60;++i) b[i]=(X>>i)&1; for(i=1;i<=n;++i) scanf("%lld",&a[i]); sort(a+1,a+n+1); t=rt=1; for(i=1;i<=n;++i){ p=ask(rt,59,a[i])+1; insert(rt,59,a[i]); an=(an+p)%mo; } printf("%d",an); return 0; }