子集卷积

子集卷积是这样的问题：

\[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)\)的时间复杂度内解决了。