子集卷积
子集卷积是这样的问题:
$$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)$的时间复杂度内解决了。
子集卷积是这样的问题:
$$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)$的时间复杂度内解决了。