题解：P12521 [Aboi Round 1] ATRI
缪凌锴_Mathew
·
·
题解
考虑操作树，x 为深度为奇数的数的异或和，归纳可得深度为奇数的点数在模 3 固定。
转化为：
给定 n,m 和大小为 n 的可重集 S。
求有多少种 S 的子集 T 的异或和，且 |T|\equiv m\pmod 3。
显然有 O(nV) 的 dp 做法。
设 S 的（异或空间）线性基大小为 C。显然最多 2^C 种数可以被凑出。
大胆猜测，当 n 大于某个阈值 B 时，直接输出这 2^C 种数。
```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)$。