自动搬运

查看原文

来自洛谷，原作者为

	缪凌锴_Mathew 希↑望→计↓划↑可→以↑成↓功↓ | 离错真机

搬运于2025-08-24 23:16:09，当前版本为作者最后更新于2025-05-21 18:46:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑操作树，$x$ 为深度为奇数的数的异或和，归纳可得深度为奇数的点数在模 $3$ 固定。

转化为：

给定 $n,m$ 和大小为 $n$ 的可重集 $S$。

求有多少种 $S$ 的子集 $T$ 的异或和，且 $|T|\equiv m\pmod 3$。

显然有 $O(nV)$ 的 dp 做法。

设 $S$ 的（异或空间）线性基大小为 $C$。显然最多 $2^C$ 种数可以被凑出。

大胆猜测，当 $n$ 大于某个阈值 $B$ 时，直接输出这 $2^C$ 种数。

$n\le B$ 时跑 $O(nV)$ 的 dp。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1<<16;
const int MAXL=4e4+10;
const int L=4e4;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m;
int t[MAXL];
bool dp[3][MAXN],lst[3][MAXN];
namespace basis{
	int S=0;
	int lb[16];
	inline void ins(int x){
		for(int i=15;~i;i--)
		{
			if(x&(1<<i)){
				if(!lb[i]){
					lb[i]=x;
					S|=1<<i;
					return ;
				}
				x^=lb[i];
			}
		}
	}
	inline void clr(){
		S=0;
		memset(lb,0,sizeof(lb));
	}
	inline void prt(){
		basic_string <int> ans;
		ans.push_back(0);
		for(int s=S;s;s=(s-1)&S)
		{
			int x=0;
			for(int i=0;i<16;i++)
			{
				if(s&(1<<i)){
					x^=lb[i];
				}
			}
			ans.push_back(x);
		}
		sort(ans.begin(),ans.end());
		for(int x:ans)
		{
			printf("%d ",x);
		}
		putchar('\n');
	}
}
inline void solve(){
	scanf("%d",&n);
	m=t[n];
	if(n>=82){
		basis::clr();
		while(n--)
		{
			int x;
			scanf("%d",&x);
			basis::ins(x);
		}
		basis::prt();
		return ;
	}
	memset(dp,false,sizeof(dp));
	dp[0][0]=true;
	while(n--)
	{
		int x;
		scanf("%d",&x);
		memcpy(lst,dp,sizeof(dp));
		for(int a:{0,1,2})
		{
			for(int i=0;i<(1<<16);i++)
			{
				if(lst[a][i]){
					dp[(a+1)%3][i^x]=true;
				}
			}
		}
	}
	for(int i=0;i<(1<<16);i++)
	{
		if(dp[m][i]){
			printf("%d ",i);
		}
	}
	puts("");
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	t[1]=1;
	t[2]=2;
	for(int i=3;i<=L;i++)
	{
		t[i]=(i+3-t[i-1])%3;
	}
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}

发现过了。怎么回事呢。

先别急，这不是一篇乱搞题解。

可以证明，这种做法是对的。

相当于证明：

$B-\log V$ 个数一定可以凑出集合 $T$ 使得 $|T|\bmod 3$ 可以是 $0/1/2$ 且 $T$ 异或和为 $0$。

发现凑出 $T_1,T_2$ 使得 $|T_1|\bmod 3\ne 0,|T_2|\bmod 3\ne 0$ 即可。

结论：$2\log V+1$ 个数一定可以凑出一个集合 $T$ 使得 $|T|\not\equiv0\pmod 3$ 且 $T$ 异或和为 $0$。

证明：

取 $2\log V+1=33$ 个数，称其集合为 $A$。

其中最多 $\log V=16$ 个数属于 $A$ 的线性基，称为 $x_1,x_2,\dots,x_{16}$。

若干个 $x$ 的异或和可以表示 $A$ 中所有数。

剩下的 $\log V+1=17$ 个数称为 $y_1,y_2,\dots,y_{17}$。

对于 $i$，$y_i$ 可表示为 $k_i$ 个 $x_i$ 的异或和。

• $k_i+1\not\equiv 0\pmod 3$，那么取 $y_i$ 和它对应的这 $k_i$ 个 $x$ 即可。
• 否则 $k_i\equiv 2\pmod 3$。

根据线性基结论，$\log V+1=17$ 个数的线性基一定满，一定可以提取一个子集异或和为 $0$。

必有 $y_{p_1}\oplus y_{p_2}\oplus\dots\oplus y_{p_c}=0$。

• 若 $c\not\equiv 0\pmod 3$，取这 $c$ 个 $y$ 即可。
• 否则将 $y_{p_1}$ 替换成其对应的 $k_{p_1}$ 个 $x$，此时数量为 $c-1+k_{p_1}\equiv 1\pmod 3$。

所以 $B$ 有下界 $2\times(2\log V+1)+\log V=82$。

时间复杂度 $O(n\log V+V\log V)$。