集合幂级数小记

集合幂级数：F(x)=∑SfSxS

卷积：[xk]F∗G=∑i,j[i⊕j=k]figj

FWT、IFWT 的公式不写了，随便查/cy

注意事项：

1. O(2nn2) 可以跑 n=20，但是很卡。

2. cache 友好：先循环 i，再循环 j，再循环 s。（玄学优化）

3. IFWT 单点求值：​or=∑T⊆S(−1)|S|−|T|fT,and=∑S⊆T(−1)|T|−|S|fT

4. FWT 可以用来加速集合反演！ansS=∑S⊆T(−1)|T|−|S|fT，这不就是↑那个 and 的 IFWT 吗qwq（O(3n)→O(2nn)）

5. 一般难题不考裸玩，需要 FWT 之后存下来，过一段时间之后乘上一堆再 IFWT 回去

6. 集合幂级数也可以玩 exp，ln，exp 的组合意义：从一个集合中选出若干个无序的互不相同的子集，ln 主要是配套 exp 套公式用的。

7. 求导大法，用导数表示自己，对 exp 和 ln 都管用

本文作者：CharlieVinnie

本文链接：https://www.cnblogs.com/Charlie-Vinnie/p/15824451.html

版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。

I solemnly swear that I am up to no good