洛谷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\) 满足： \[ c_k=\sum_{(i \lor j) = k,~(i \land j) = 0} a_i b_j \] 其中 \(\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}\) 为答案，那么 \[ h_i = \sum_{k=0}^i f_k *g_{i-k} \] 其中 \(*\) 表示子集并卷积运算，那么答案 \(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;
}参考文献：
