[UOJ310] 黎明前的巧克力

Sol

某比赛搬了这题。

首先选择两个不交非空子集且异或和为0的方案数，等价于选择一个异或和为0的集合，并把它分成两部分的方案数。
这显然可以DP来算，设 \(f[i][j]\) 表示前\(i\)个数异或和为\(j\)的方案数，那么转移就是 \(f[i][j]=f[i-1][j]+2\cdot f[i-1][j\;\text{xor}\;a[i]]\)

如果设 \(b_i[0]=1,b_i[a[i]]=2,b_i[j]=0\)，那么这个转移就是求\(f\)与\(b_i\;\text{xor}\)卷积的过程，可以用FWT优化，但是复杂度似乎更爆炸了。

如果我们可以把每个\(b\) FWT之后的结果都求出来并乘在一起，最后在对应位置乘到\(f\)上，再把\(f\) IFWT回去不就好了嘛！

如果把\(b_i\)数组FWT之后的结果打印出来，会发现所有位置不是\(3\)就是\(-1\)，大概是因为这个\(2\)对每一项的贡献要么是\(2\)要么是\(-2\)。

我们可以先把\(b_i\)数组整个加起来，对它做一次FWT。

因为FWT的和等于和的FWT。对于FWT之后的第\(i\)项\(s\)，设这位有\(x\)个数为\(-1\)，那么就有\(n-x\)个数为 \(3\)，且\(3(n-x)-x=s\)，解得 \(x=\large \frac{3n-s}4\) 。那么FWT之后这一项的值就是 \((-1)^x3^{n-x}\)。

然后乘到\(f\)上再IFWT回去就行了。

（uoj被卡了我不知道这代码能过否
（mp数组开小了，已经改过来了

Code

#include
#include