题解 P6097 【【模板】子集卷积】

· · 题解

萌新由于太弱被卡了常。那一定是FMT自身常数太大了

如果不会 FMT 可以移步谷谷的板子题或者我的博客

快速子集变换(FST)是在 FMT 基础上的扩展，解决的也是子集交卷积，但是限制了状态不重复，即

c_i=\sum_{\begin{aligned}~k &\cup j=i\\ k &\cap j= \emptyset \end{aligned}}a_kb_j

换个写法：

c_s=\sum_{t\subseteq s}a_sb_{s-t}

这东西其实也不是非要用 FMT 来做，FWT 也可以。

然后就是考虑在卷积的时候多增加一维，即 f_{i,S} 表示集合 S 中有 i 个元素，于是发现只有当元素个数相加符合时才是对的。

于是一开始将 f_{bct(s),s} 赋值为 f_s，其中 bct(s)=\rm bitcount(s)。然后对每一个 f_i 分别做 FMT，之后按位乘的时候需要

P_{i, S}=\sum_{i=0}^{i} f_{j, S} \times g_{i-j, S}

输出的时候只输出 P_{bct(s),s} 即可。

复杂度似乎是两个 \log 的？然而并不满。推荐取模优化。

#define MAXN 21
#define MAXM 2000010
#define Mod 1000000009

#define I inline
#define LL long long

using namespace std;
int bc[MAXM];
int N, M;
int A[MAXN][MAXM], B[MAXN][MAXM], C[MAXN][MAXM];

I int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
I void reduce(int &x) { x += x >> 31 & Mod; }
I void Ifmt(int *f) {
    register int i, j;
    for (i = 0; i < N; ++i)
        for (j = 0; j <= M; ++j)
            if (j >> i & 1)
                reduce(f[j] -= f[j ^ 1 << i]);
}
I void fmt(int *f) {
    register int i, j;
    for (i = 0; i < N; ++i)
        for (j = 0; j <= M; ++j)
            if (j >> i & 1)
                reduce(f[j] += f[j ^ 1 << i] - Mod);
}
int main() {
    cin >> N;
    M = (1 << N) - 1;
    register int i, j, s;
    for (i = 1; i <= M; ++i) bc[i] = bc[i - (i & -i)] + 1;
    for (i = 0; i <= M; ++i) A[bc[i]][i] = read();
    for (i = 0; i <= M; ++i) B[bc[i]][i] = read();
    for (i = 0; i <= N; ++i) fmt(A[i]), fmt(B[i]);
    for (i = 0; i <= N; ++i)
        for (j = 0; j <= i; ++j)
            for (s = 0; s <= M; ++s) (C[i][s] += 1ll * A[j][s] * B[i - j][s] % Mod) %= Mod;
    for (i = 0; i <= N; ++i) Ifmt(C[i]);
    for (i = 0; i <= M; ++i) printf("%d ", C[bc[i]][i]);
}