今天一个集训队互测的前置题，补了感觉不错，所以写篇题解（
题目链接
题意
现在有 块巧克力与两个人，第
块巧克力权值为 。
定义一种选巧克力的方案是合法的，当且仅当：
- 两个人选的巧克力不重复；
- 两个人选的巧克力，权值的异或和相等；
- 两个人加在一起，至少选择了一个巧克力。
求合法方案数，对
取模。
题解
首先会发现，两个人选的巧克力异或和相等，就相当于所有被选中的巧克力，异或和是
。
那么对于每一个异或和为 的子集
，他的贡献就是 。
所以我们只需要算出上述值，并减去 （空集）即可。
暴力 dp 是容易的，这里就不写了。
我们目前的主要目标是快速对所有异或和为 的子集计数。
不难发现，这个很像 FWT 所能干的事情。考虑使用异或卷积去做。
每一种数字 有两种选择：
- 不选，对异或和有
的贡献，对权值有 的贡献；
- 选，对异或和有
的贡献，对权值有 的贡献。
所以我们可以构造出多项式 ，其中 。
我们计算即可 即可，其中
为异或卷积。
所以我们可以在
的复杂度内计算出答案（还不如暴力dp。
仔细回想 FWT 的式子，对于一个多项式 ： 而我们所有的多项式 ，都最多只有两项。 这就意味着，多项式 中，每一项的系数只能是 或 。
下面才是这道题的重点。
首先我们发现 具有分配律，即
。
那么就会有 。
这个式子是容易求的。我们设它是多项式 。
而我们想要求的其实是 ，其中 是按位乘。
根据前面的结论，我们又知道对于
的每一位 ，它可以被表示为 的形式，并且我们知道
。
而我们已经知道 了，那么就有
，那我们就知道
。
这样，我们就可以把
求出来了。
而
就是答案，所以我们直接将得到的
做一个 即可。
时间复杂度 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
const ll inv2=(mod+1)/2;
const int L=1048576;
ll a[1048576];
ll p[1000001];
inline void FWT(int typ)
{
for(int len=1;len<L;len<<=1) for(int i=0;i<L;i++) if(!(i&len))
{
int num1=a[i],num2=a[i^len];
if(typ) a[i]=num1+num2,a[i^len]=num1-num2;
else a[i]=(num1+num2)*inv2%mod,a[i^len]=(num1-num2+mod)*inv2%mod;
}
}
int n;
int main()
{
n=read(),p[0]=1;
for(int i=1;i<=n;i++) a[0]++,a[read()]+=2,p[i]=p[i-1]*3%mod;
FWT(1);
for(int i=0;i<L;i++)
{
int A=(n+a[i])/4,B=(3*n-a[i])/4;
a[i]=p[A];if(B&1) a[i]=(mod-a[i])%mod;
}
FWT(0);
printf("%lld\n",(a[0]-1+mod)%mod);
return 0;
}
|