【OI之路】03数论-19集合幂级数

集合幂级数学习笔记(vfk在15年的论文)

集合幂级数 $f=\sum_{S \subseteq 2^U} f_S x^S$
加减法很好定义,对于乘除法,我们可以自行定义各种运算

集合并卷积:
$[S_1 \bigcup S_2 \subseteq S]=[S_1 \subseteq S][S_2 \subseteq S]$
那么加减乘都资瓷了,这个卷积的逆运算的话,就是在点值表达式下直接除
不能理解原理的话,把check写出来,不用运行你都会发现是正确的……
甚至开高次根都是直接开……

集合对称差卷积
$[S=\emptyset]=\frac{1}{2^n} \sum_{T \subseteq U} (-1)^{|T \bigcap S|}$
那么现在的柿子就是 $B_S=\sum_{T \subseteq U} (-1)^{|T \bigcap S|} A_T$
考虑递推,B[S][i]表示当前只统计和S的异或值为 $2^i-1$ 的子集的T
那么每次把这一位不同、后面相同、前面任意的统计进去(然后你会发现自己没有被统计,应作为B[S][-1])
$B[S][i]=B[S][i-1]-B[S|2^i][i-1],B[S|2^i]=B[S][i-1]+B[S|2^i][i-1]$
然后有个更简单的写法: $B[S][i]=B[S][i-1]+B[S|2^i][i-1],B[S|2^i]=B[S][i-1]-B[S|2^i][i-1]$
这个就不用前面那步了,本质上是一样的,因为 B[S|2^i][i-1] 里面这一位都是1,等价于把-1放到中间去乘

子集卷积
或为S并为空,相当于两个不重叠集合的拼接,感觉不少状压都是这种形式
将条件转化为 $a \bigcup b=S,|a|+|b|=|S|$
可以看作是一个集合幂级数的或运算(异或也行)套一个形式幂级数的乘法,暴力枚举做即可,但要去除没有意义的地方
然后逆运算的话,和上面思路不太一样
考虑每个位置在点值表达法下, $C_t=\sum A_i B_{t-i}$
那么现在求B的话可以递推,把其他B移到左边,除A0即可
开单个根的话也能开

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8434.html
转载请注明出处,谢谢!