【模板】子集卷积

题目链接：luogu P6097

题目大意

给你两个长度为 2^n 的序列 a,b，要你求一个序列 c 满足：
c[k]=sum(i&j=0,i|j=k)a[i]b[j]

思路

\(c_k=\sum\limits_{i\&j=0,i|j=k}a_ib_j\)
首先考虑只有一个条件 \(i|j=k\)：那就是一个或的卷积，直接用 FWT。
考虑处理 \(i\&j=0\)：
发现就是两边不能有一个位置都是 \(1\)，或者说我们设 \(num1_i\) 为 \(i\) 二进制 \(1\) 的个数，就会有 \(num1_i+num1_j=num1_{i| j}\)

那我们考虑开 \(n\) 个 FWT，然后每个位置 \(i\) 的值一开始放在 \(num1_i\) 的位置。
然后跑 FWT 之后我们就 DP：\(f_{k,S}=\sum\limits_{i+j=k}f_{i,S}f_{j,S}\)
然后再 IFWT 回去就是答案了（注意第 \(i\) 个位置的答案也是放在 \(num1_i\) 的位置）。

代码

#include
#define mo 1000000009

using namespace std;

int n, f[21][1 << 20], g[21][1 << 20], h[21][1 << 20];

int num1(int x) {
	int re = 0;
	while (x) {re++; x -= x & (-x);}
	return re;
}

int jia(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int jian(int x, int y) {return x < y ? x - y + mo : x - y;}
int cheng(int x, int y) {return 1ll * x * y % mo;}

void FWT(int *f, int limit, int op) {
	for (int mid = 1; mid < limit; mid <<= 1) {
		for (int R = mid << 1, j = 0; j < limit; j += R) {
			for (int k = 0; k < mid; k++) {
				int x = f[j | k], y = f[j | mid | k];
				f[j | k] = x; f[j | mid | k] = jia(cheng(x, op), y);
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < (1 << n); i++) scanf("%d", &f[num1(i)][i]);
	for (int i = 0; i < (1 << n); i++) scanf("%d", &g[num1(i)][i]);
	
	for (int i = 0; i <= n; i++) {
		FWT(f[i], 1 << n, 1); FWT(g[i], 1 << n, 1);
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; i + j <= n; j++)
			for (int S = 0; S < (1 << n); S++) {
				h[i + j][S] = jia(h[i + j][S], cheng(f[i][S], g[j][S]));
			}
	}
	for (int i = 0; i <= n; i++) {
		FWT(h[i], 1 << n, mo - 1);
	}
	
	for (int i = 0; i < (1 << n); i++) printf("%d ", h[num1(i)][i]);
	
	return 0;
}