记得去年省选二试前我翻开vfk的集合幂级数论文,想要学习一波。
然而一年过去了,我发现我好像还没学。于是又是一年省选将至,我还是赶快把坑填了吧。
先定义两个主角
集合并卷积
定义和
的集合并卷积
如下
我们关注
这里有一个相等的限制,一般这种限制我们不容易直接解决。回忆解决这类问题的方法,不妨考虑把相等改为子集的约束,再通过容斥求答案。
根据上面的思路,不妨设
这启发我们定义一种变换
同时由容斥原理得
此时我们发现
卷积转化为了点积,加速了计算。
我们知道了上面这种变换有一个优美的名字叫快速莫比乌斯变换(Fast Mobius Transform, FMT),可以在的时间完成一次变换或者逆变换。这无疑比暴力计算的效率高多了。
集合对称差卷积
定义和
的集合对称差卷积
如下
我们关注
首先考虑一个等式
代入原式化简
令
则
大概是一个比较套路的反演?和上面类似,我们发现这里面也有一些类似的形式,启发我们定义这样的变换
和逆变换
此时我们发现
卷积又转化为了点积,又加速了计算。
我们同样知道上面这种变换也有一个优美的名字叫快速沃尔什变换(Fast Walsh Transform, FWT),可以在的时间完成一次变换或者逆变换。这无疑又比暴力计算的效率高多了。