「题解」300iq Contest 2 B Bitwise Xor

本文将同步发布于：

题目

题目链接：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<x\)。

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

对于位置第一个不同的位置 \(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<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\n",ans);

	return 0;

}

巴特西