子集卷积与bitcount

如果一个卷积长这样：

$$f(S) = \sum_{X\cup Y=S,X\cap Y = \emptyset} g(X)\times h(Y)$$

好像不能够直接用FWT做了呢。但是我们观察，$X\cup Y=S,X\cap Y=\emptyset$等价于：

$$\begin{cases} X\cup Y=S\\ |X|+|Y|=|S| \end{cases}$$

正确性显然。那么，我们可以枚举集合的大小，然后做或卷积。可以先对所有的进行FWT，然后枚举大小、求和，最后再变换回去。时间复杂度$2^n n^2$，$n$表示元素的数量。

其实这也是对付某些位运算关系特别复杂的题的一种套路吧。尽量用$bitcount$取代替式子中的位运算条件，最后按$bitcount$分组算FWT卷积。

例题：
WC2018 州区划分
hdu6057 Kanade’s convolution