本文将同步发布于：
题目
题目链接：gym102331B。
题意概述
给你一个长度为 (n) 的序列 (a_i)，求一个最长的子序列满足所有子序列中的元素两两满足 (a_ioplus a_jgeq x)，其中 (oplus) 表示按位异或。
题解
发现性质
我们发现 (poplus qgeq x) 这个性质不是很好处理，决定通过研究异或的性质来解决问题。
我们考虑一个数 (a)，若其满足 (< x)，那么一定满足下面的情况：
- 存在一个 (i) 满足 (a) 与 (x) 在 ([i+1,infty)) 位上相同，在第 (i) 位上有 (a<x)。
我们考虑 (poplus q<x)，发现：
对于位置第一个不同的位置 (i)，必然有 (x_i=1,p_i=q_i)，而不是 (p_i eq q_i)。
因此我们可以发现，对于三个数 (a,b,c)，若其满足 (aleq bleq c)，一定有 (min{aoplus b,boplus c}leq aoplus c)。
动态规划
得到了上面的性质，我们不难发现，如果我们将 (a) 从小到大排序，那么异或的最小值一定会出现在子序列的相邻两项之间。
换句话说，我们只需要保证子序列的所有相邻的项的异或 (geq x)，我们得到的就是一个合法的子序列。
设 (f_i) 表示以 (i) 结尾的最长的合法子序列，那么有转移方程：
[f_i=max_{a_ioplus a_jgeq x}{f_j}+1
]
时间复杂度为 (Theta(n^2))。
数据结构优化 dp
考虑到上面的转移与异或有关，我们不难想到可以利用 01-Trie 来优化转移过程。
具体地，我们在 Trie 上维护子树中 (f_i) 的最大值，每次转移时在 Trie 上根据与 (x) 的异或值选择左右儿子，如果另一棵子树内的所有值都满足 异或后 (geq x)，那么我们更新答案。
时间复杂度为 (Theta(nlog_2a))。
参考程序
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
return res;
}
inline ll readll(void){
reg char ch=getchar();
reg ll res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
return res;
}
const int MAXN=3e5+5;
const int MAXLOG2A=60;
const int mod=998244353;
inline int add(reg int a,reg int b){
a+=b;
return a>=mod?a-mod:a;
}
inline int sub(reg int a,reg int b){
a-=b;
return a<0?a+mod:a;
}
inline int fpow(reg int x,reg int exp){
reg int res=1;
while(exp){
if(exp&1)
res=1ll*res*x%mod;
x=1ll*x*x%mod;
exp>>=1;
}
return res;
}
int n;
ll x;
ll a[MAXN];
namespace Trie{
const int MAXSIZE=MAXN*50;
struct Node{
int ch[2];
int sum;
#define ch(x) unit[(x)].ch
#define sum(x) unit[(x)].sum
};
int tot;
Node unit[MAXSIZE];
inline void Init(void){
tot=1;
return;
}
inline void insert(reg ll x,reg int val){
reg int p=1;
for(reg int i=MAXLOG2A-1;i>=0;--i){
reg int c=(x>>i)&1;
if(!ch(p)[c])
ch(p)[c]=++tot;
sum(p)=add(sum(p),val);
p=ch(p)[c];
}
sum(p)=add(sum(p),val);
return;
}
inline int query(reg ll v){
reg int p=1;
reg int res=0;
for(reg int i=MAXLOG2A-1;i>=0;--i){
reg int cv=(v>>i)&1,cx=(x>>i)&1;
if(!cx)
res=add(res,sum(ch(p)[!cv]));
p=ch(p)[cx^cv];
}
if(p)
res=add(res,sum(p));
return res;
}
#undef ch
#undef sum
}
int main(void){
n=read(),x=readll();
for(reg int i=0;i<n;++i)
a[i]=readll();
sort(a,a+n);
Trie::Init();
reg int ans=0;
for(reg int i=0;i<n;++i){
reg int val=add(1,Trie::query(a[i]));
Trie::insert(a[i],val);
ans=add(ans,val);
}
printf("%d
",ans);
return 0;
}