请大家注意：
因为作者写的文章中的梯等式公式总是莫名的显示错误，所以作者的许多文章中的梯等式都暴力拆成一步一个等式了。
造成的不适，请谅解。
同时，如果文章中还有其他错误，请联系作者，谢谢。
问题模型
快速求。
公式推导
原式等价与：
那么我们设：
就有：
之后可以用之前的子集反演得到：
现在问题就是如何快速的在与
之间变换。
由于的枚举子集过于简单，就不讲了，在这里介绍
的做法：
我们先考虑正变换，考虑递推：
设表示
那么我们有：
然后对于所有不包含这个元素的集合
，有：
那么即为所求。
接下来我们考虑反演，求出答案：
我们类似的定义，那么对于所有不包含
这个元素的集合
，有：
最后即为所求。
又因为每一位（每一个元素）是独立的，所以我们可以从而不是从
。
那么我们就做完了。
拓展
：集合交卷积
这个也是可以做集合交卷积的。
因为 =
所以我们在进行变换之前先将每个值和它的补集交换一下，
在变换之后在交换一次，就好了。
拓展
：子集卷积
其实就是在并集的基础上有加了一个条件：。
这样我们只需要再加一维表示集合的大小，就好了。
网友评论