請大家注意：

因為作者寫的文章中的梯等式公式總是莫名的顯示錯誤，所以作者的許多文章中的梯等式都暴力拆成一步一個等式了。
造成的不適，請諒解。
同時，如果文章中還有其他錯誤，請聯(lián)系作者，謝謝。

問題模型

快速求。

公式推導(dǎo)

原式等價與：


那么我們設(shè)：

就有：

之后可以用之前的子集反演得到：

現(xiàn)在問題就是如何快速的在與之間變換。
由于的枚舉子集過于簡單，就不講了，在這里介紹的做法：
我們先考慮正變換，考慮遞推：
設(shè)表示
那么我們有：
然后對于所有不包含這個元素的集合，有：


那么即為所求。
接下來我們考慮反演，求出答案：
我們類似的定義，那么對于所有不包含這個元素的集合，有：


最后即為所求。
又因為每一位（每一個元素）是獨立的，所以我們可以從而不是從。
那么我們就做完了。

拓展：集合交卷積

這個也是可以做集合交卷積的。
因為 =
所以我們在進(jìn)行變換之前先將每個值和它的補(bǔ)集交換一下，
在變換之后在交換一次，就好了。

拓展：子集卷積

其實就是在并集的基礎(chǔ)上有加了一個條件：。
這樣我們只需要再加一維表示集合的大小，就好了。