洛谷P6097 【模板】子集卷积 题解
题目链接：P6097 【模板】子集卷积
题意：
给定两个长度为 $2^n$ 的序列 $a_0,a_1,\cdots,a_{2^n-1}$ 和 $b_0,b_1,\cdots,b_{2^n-1}$
你需要求出一个序列 $c_0,c_1,\cdots,c_{2^n-1}$，其中 $c_k$ 满足：
其中 $\lor$ 表示按位或，$\land$ 表示按位与。答案对 $10^9+9$ 取模。
输入格式：
第一行输入一个正整数 $n$ ，表示集合的大小。
第二行有 $2^n$ 个整数，描述了 $a$。
第三行有 $2^n$ 个整数，描述了 $b$。
输出格式：
输出一行 $2^n$ 个整数，表示 $c$。
数据范围：
$1\le n\le 20$，$0\le a_i,b_i< 10^9+9$。
才发现这个 $2^n-1$ 个数就是 $n$ 个元素的所有非空集合，$a_i,b_i$ 就是集合 $i$ 的两种权值。
称 $c_k = \sum_{(i \lor j) = k} a_ib_j$ 为「子集并卷积」运算。显然这个可以用 FWT 在 $\mathcal{O}(n \log n)$ 的复杂度内计算出来。
考虑原题，第一个限制 $(i \lor j) = k$ 很简单，直接 FWT 就可以。
第二个限制 $(i \land j) = 0$ ，也就是 $S_i \cap S_j = \varnothing$ ，这等价于 $|S_i| + |S_j|=|S_i \cup S_j|$
考虑额外开一维记录元素个数。即，设 $f_{i,j} = a_j\times [|j|=i],~g_{i,j} = b_j[|j|=i]$
并类似的设 $h_{i,j}$ 为答案，那么
其中 $*$ 表示子集并卷积运算，那么答案 $c_i = h_{|i|,i}$ 。
时间复杂度 $\mathcal{O}(n^22^n)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
#define popc(x) __builtin_popcountll(x)
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N 21
int a[N + 1][1 << N], b[N + 1][1 << N], c[N + 1][1 << N];
void fwt(int *f, int n, int sgn) // OR
{
for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) // n = END + 1
for(int i = 0; i < n; i += o) for(int j = 0; j < k; j++)
add(f[i + j + k], (sgn > 0) ? f[i + j] : mod - f[i + j]);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n; cin >> n; int mx = 1 << n;
rep(i, 0, mx - 1) cin >> a[popc(i)][i];
rep(i, 0, mx - 1) cin >> b[popc(i)][i];
rep(i, 0, n) { fwt(a[i], mx, 1); fwt(b[i], mx, 1); }
rep(i, 0, n) rep(j, 0, i) rep(k, 0, mx - 1)
add(c[i][k], a[j][k] * b[i - j][k] % mod);
rep(i, 0, n) fwt(c[i], mx, -1);
rep(i, 0, mx - 1) cout << c[popc(i)][i] << " \n"[i == mx - 1];
return 0;
}参考文献：
