题意

有n种元素，则共有\(2^n\)个不同的集合。

求所有选择集合的方案，使得选择的集合的并集大小为4的倍数。

Solution

考虑\(f(k)\)，表示并集大小至少为k的选择集合方案数。

容易得到\(f(k)=C_{n}^{k}(2^{2^{n-k}}-1)\)

我们考虑构造一个容斥系数\(\alpha(k)\)，使得满足如下等式：

\(ans=\sum_{k=0}^{n} f(k) \alpha(k)\)

我们考虑每一个方案的贡献，设这个方案中集合的并集大小是\(x\)，那么显然有它的贡献为\([4|x]\)

我们考虑这个方案在哪里被计算过，显然是所有\(k<=x\)的\(f(k)\)

于是其贡献亦可以被表示为\(\sum_{k=0}^x C_{x}^{k} \alpha(k)\) ，其中C的意思即为钦定这k个是被\(f(k)\)统计到的k个。

于是有：\([4 \mid x]=\sum_{k=0}^x C_{x}^{k} \alpha(k)\)

根据二项式反演，\(\alpha(x) = \sum_{k=0}^{x} (-1)^{x-k} C_{x}^{k} [4 \mid k]\)

接下来引入单位根反演：

\(\forall k,有[n \mid k]=\frac{1}{n} \sum_{i=0}^{n-1} \omega_{n}^{ik}\)

证明：

显然，当\(n \mid k\)时，\(ik\)为\(n\)的倍数，右边式子即为\(\frac{1}{n} \times n = 1\)

而\(n \nmid k\)时，后面的式子是一个等比数列求和，可以发现分子始终为0。

那，把这个单位根反演暴力代入上式

\[\begin{aligned} \alpha(x) &= \sum_{k=0}^{x} (-1)^{x-k} C_{x}^{k} \frac{1}{4} \sum_{i=0}^{3} \omega_{4}^{ik}\\ \alpha(x) &= \frac{1}{4} \sum_{i=0}^{3} \sum_{k=0}^{x} C_{x}^{k} (-1)^{x-k} (\omega_{4}^{i})^{k}\\ \alpha(x) &= \frac{1}{4} \sum_{i=0}^{3} (-1+\omega_{4}^{i})^x \\ \end{aligned} \]

然后就可以求了，注意要做到严格\(O(n)\)。

对于\(f\)的部分，预处理即可做到\(O(n)\)；对于\(\alpha\)的部分，动态维护\(\omega\)即可。