子集卷积

FWT 的简单运用

问题

考虑如下问题：
$$
h(n) = (f * g)(n) = \sum_{i \& j = 0 \wedge i \mid j = n} f(i) * g(j)
$$
也就是 $h(n)$ 等于所有把 $n$ 划分成为两个集合的方案权值积的和，也可以写成集合形式，即求：
$$
h(S) = (f * g)(S) = \sum_{A \cap B = 0 \wedge A \cup B = S} f(A) * g(S)
$$
所以叫子集卷积

思路

发现比 FWT 多个条件，让人讨厌

考虑限制，设 $f’(i, S) = \sum_{\mid T \mid = i \wedge T \in S} f(T)$ ，这样的好处是， $i$ 记录了 $T$ 的大小，那么要保证 $i + j = \mid S \mid$ ，就可以保证对应子集没有交集了

那么如何求 $f’(i, S)$ 呢？我们先符初始值 $f’(\mid S \mid, S) = f(S)$ ，然后直接对 $f’(\mid S \mid)$ 做或卷积，就可以得到所有 $f’(\mid S \mid, X)$ 了

时间复杂度 $O(n \log^2 n)$ ，其中 $n$ 是多项式长度

代码

子集卷积

#include <bits/stdc++.h>
#define pct(x) __builtin_popcount(x)
using LL = long long;
const int N = (1 << 20) + 100, P = 1e9 + 9, BT = 20 + 5;
int bit, n, f[BT][N], g[BT][N], h[BT][N];
void adj(int &x){ x += (x >> 31) & P; }
void fwt(int x[], int len)
{
	for (int i = 2; i <= len; i <<= 1)
		for (int mid = i >> 1, j = 0; j < len; j += i)
			for (int k = j; k < j + mid; ++k) adj(x[k + mid] += x[k] - P);
}
void ufwt(int x[], int len)
{
	for (int i = 2; i <= len; i <<= 1)
		for (int mid = i >> 1, j = 0; j < len; j += i)
			for (int k = j; k < j + mid; ++k) adj(x[k + mid] -= x[k]);
}
int main()
{
	scanf("%d", &bit), n = (1 << bit);
	for (int i = 0; i < n; ++i) scanf("%d", &f[pct(i)][i]);
	for (int i = 0; i < n; ++i) scanf("%d", &g[pct(i)][i]);
	for (int i = 0; i <= bit; ++i) fwt(f[i], n), fwt(g[i], n);
	for (int i = 0; i <= bit; ++i)
		for (int j = 0; j + i <= bit; ++j)
			for (int s = 0; s < n; ++s) adj(h[i + j][s] += LL(f[i][s]) * g[j][s] % P - P);
	for (int i = 0; i <= bit; ++i) ufwt(h[i], n);
	for (int i = 0; i < n; ++i) printf("%d ", h[pct(i)][i]);
	return 0;
}