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