集合幂级数小记 ????

发布于 1970年 01月 01日 08:00

集合幂级数:F(x)=SfSxS

卷积:[xk]FG=i,j[ij=k]figj

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

注意事项:

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

2. cache 友好:先循环 i,再循环 j,再循环 s。(玄学优化)

3. IFWT 单点求值:or=TS(1)|S||T|fT,and=ST(1)|T||S|fT

4. FWT 可以用来加速集合反演!ansS=ST(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