「题解」300iq Contest 2 B Bitwise Xor

本文将同步发布于：

• 洛谷博客；
• csdn；
• ；
• gym102331B。

  题意概述

  给你一个长度为 \(n\) 的序列 \(a_i\)，求一个最长的子序列满足所有子序列中的元素两两满足 \(a_i\oplus a_j\geq x\)，其中 \(\oplus\) 表示按位异或。

  题解

  发现性质

  我们发现 \(p\oplus q\geq x\) 这个性质不是很好处理，决定通过研究异或的性质来解决问题。

  我们考虑一个数 \(a\)，若其满足 \(< x\)，那么一定满足下面的情况：

  • 存在一个 \(i\) 满足 \(a\) 与 \(x\) 在 \([i+1,\infty)\) 位上相同，在第 \(i\) 位上有 \(a。

  我们考虑 \(p\oplus q，发现：

  对于位置第一个不同的位置 \(i\)，必然有 \(x_i=1,p_i=q_i\)，而不是 \(p_i\neq q_i\)。

  因此我们可以发现，对于三个数 \(a,b,c\)，若其满足 \(a\leq b\leq c\)，一定有 \(\min\{a\oplus b,b\oplus c\}\leq a\oplus c\)。

  动态规划

  得到了上面的性质，我们不难发现，如果我们将 \(a\) 从小到大排序，那么异或的最小值一定会出现在子序列的相邻两项之间。

  换句话说，我们只需要保证子序列的所有相邻的项的异或 \(\geq x\)，我们得到的就是一个合法的子序列。

  设 \(f_i\) 表示以 \(i\) 结尾的最长的合法子序列，那么有转移方程：

  \[f_i=\max_{a_i\oplus a_j\geq x}\{f_j\}+1 \]

  时间复杂度为 \(\Theta(n^2)\)。

  数据结构优化 dp

  考虑到上面的转移与异或有关，我们不难想到可以利用 01-Trie 来优化转移过程。

  具体地，我们在 Trie 上维护子树中 \(f_i\) 的最大值，每次转移时在 Trie 上根据与 \(x\) 的异或值选择左右儿子，如果另一棵子树内的所有值都满足 异或后 \(\geq x\)，那么我们更新答案。

  时间复杂度为 \(\Theta(n\log_2a)\)。

  参考程序

  #include
  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