子集卷积是这样的问题:

$$f_S=\sum_{T\subset S} g_Th_{S-T}$$

给定$g,h$求$f$。

考虑上面这个式子相当于

$$f_S=\sum_{G\cup H=S,G\cap H=\varnothing}g_Gh_H$$

发现$|S|=|G\cup H|=|G|+|H|-|G\cap H|=|G|+|H|$,所以多记一维$|S|$就可以保证$|G\cap H|=0$了,那么就可以在$O(2^{|S|}(|S|)^2)$的时间复杂度内解决了。

标签: 数学

添加新评论