题解：P12521 [Aboi Round 1] ATRI

考虑操作树，

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。

CPP

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

。

题解：P12521 [Aboi Round 1] ATRI

文章操作

相关推荐

评论

题解：P12521 [Aboi Round 1] ATRI