【UOJ#310】【UNR#2】黎明前的巧克力
FWT
题目大意：
给定 $n$ 个数 $a_1,a_2,a_3,\ldots,a_n$。有两个人，要在其中选出两个集合（交换算两种方案），使得集合没有交集，并且两个集合的 xor 和相等。允许一个人选空集，不允许两个人同时选空集。
求方案数。
题解：
其实相当于两个人选的数的 xor 和为 $0$。
那么对每个数进行考虑，要么两个人都不选，要么其中一个人选了。
于是对于 $a_i$，有一种选法使当前的 xor 和不变，两种选法使当前的 xor 和异或上 $a_i$。
那么令 $F_{i,0}=1$，$F_{i,a_i}=2$，然后对所有 $F_i$ 做集合并卷积就好了。
这样复杂度显然爆炸。
考虑对 $A$ 进行 FWT 后得到的 $A’$，满足 $A’[k]=\sum\limits_{i}(-1)^{\mathrm{popcount}(i\&k)}A[i]$。
所以 $F_i$ 的每一位要么是 $-1$ 要么是 $3$。
那么最终点积出来的数组 $G$ 可以表示为 $G[k]=3^x\cdot (-1)^y$ 的形式。
接下来我们只需要知道每一位对应的 $x$ 和 $y$ 是多少就好了。
首先有 $x+y=n$。我们只需要知道 $x-y$ 是多少就能求出 $x$ 和 $y$。
对于 $a_i$，我们只要令 $F_{a_i}=1$，然后对 $F$ 做 FWT 就可以知道它对每位的贡献是 $1$ 还是 $-1$。而 $\mathrm{FWT}(A+B)=\mathrm{FWT}(A)+\mathrm{FWT}(B)$。
所以令 $H[i]$ 表示 $i$ 的出现次数，然后对 $H$ 做 FWT 就可以得到每个位置的 $x-y$ 了。
接着用快速幂求出 $G$ 的每个位置的值，对其 IFWT 即可。
时间复杂度 $O(n+V\log V)$。
Code：
#include<iostream>
using namespace std;
const int md=998244353,M=1048576;
typedef long long LL;
int F[M],n;
inline void upd(int&a){a+=a>>31&md;}
inline int pow(int a,int b){
int res=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)res=(LL)res*a%md;
return res;
}
void FWT(int*a){
for(int i=1;i<M;i<<=1)
for(int j=0;j<M;j+=i<<1)
for(int k=0;k<i;++k){
const int x=a[j+k],y=a[j+k+i];
upd(a[j+k]+=y-md),upd(a[j+k+i]=x-y);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0,x;i<n;++i)
cin>>x,++F[x];
FWT(F);
for(int i=0;i<M;++i){
int x=(n+F[i])*499122177LL%md,y=(n-F[i]+md)*499122177LL%md;
F[i]=pow(3,x)*((y&1)?md-1LL:1LL)%md;
}
FWT(F);
cout<<(F[0]*998243401LL+md-1)%md<<'\n';
return 0;
}