CF1119H Triple

Alex_Wei · 2022-03-19 10:50:04 · 题解

*IX. CF1119H Triple

集合幂级数相关例 9。

神仙级别的集合幂级数应用！

不妨直接考虑将三元组推广至一般情况：给出 d_i(0\leq i < m) 以及 a_{i, j}(1\leq i \leq n, 0\leq j < m)，令集合幂级数 f_i = \sum\limits_{j = 0} ^ {m - 1}d_i x ^ {a_{i, j}}，求出所有 f_i 的 异或卷积 g = \prod\limits_{i = 1} ^ n f_i。容易发现本题即 m = 3 的情况。

令 G = \hat g，F_i = \hat f_i，则 G = \prod\limits_{i = 1} ^ n F_i。这里 \prod 表示对应位置相乘。考虑 [x ^ p]F_i，根据 FWT 的定义，其为 \sum\limits_{j = 0} ^ {m - 1} (-1) ^ {p \odot a_{i, j}} d_j。如果我们能对于每一位 p 求出 [x ^ p]\prod F_i，就可以求得 G，然后 IFWT 得到 g。

所有 d_j 前系数均为 \pm 1，组合只有 2 ^ m 种。考虑对每一位求出 [x ^ p] \prod F_i 当中这 2 ^ m 种组合分别出现的次数，再快速幂。

以下讨论均基于第 p 位。

设 c_0 \sim c_{2 ^ m - 1} 表示对应组合的出现次数。若 k 的第 j 位为 1，说明 c_k 所表示的系数序列的出现次数中 d_j 的系数为 -1，否则为 1。或者说，若 k 的第 j 位为 1，则它要求 (-1) ^ {p\odot a_{i, j}} = -1，否则要求 (-1) ^ {p \odot a_{i, j}} = 1。k 的总共 m 位的限制唯一确定了一个系数序列。

求解这些未知数自然需要方程，我们需要 2 ^ m 个线性无关的方程来求解 c。这引导我们对于每个 T \subseteq \{0, 1, \cdots, m\}，仅将 z_{i, T} = {\large \oplus}_{j \in T} a_{i, j} 代入集合幂级数。考虑集合幂级数 h_T = \sum\limits_{i = 1} ^ n x ^ {z_{i, T}}，对其进行沃尔什变换得到 H_T。

考虑 c_k 对 H_T 在 p 这一位置上的值的贡献。首先，[x ^ p]H_T = \sum\limits_{i = 1} ^ n (-1) ^ {p \odot z_{i, T}}，因为根据 FWT 的线性性，x ^ {z_{i, T}} 关于 i 求和后进行 FWT 在 p 这一位上的取值，就等于每个 x ^ {z_{i, T}} FWT 后在 p 这一位上的取值之和，故有上式。

而根据 FWT 所利用的 \odot 运算符的重要性质 i \odot (j \oplus k) = (i \odot j) \oplus (i \odot k)，(-1) ^ {p\odot z_{i, T}} 就等于 \prod\limits_{j \in T} (-1) ^ {p \odot a_{i, j}}。

因此对于 c_k，因为 k 的第 j 位为 1 对应 (-1) ^ {p \odot a_{i, j}} = -1，为 0 则对应 (-1) ^ {p \odot a_{i, j}} = 1，而 仅有 j \in T 的位置才会对 (-1) ^ {p \odot z_{i, T}} 产生贡献，所以 k 对应的系数序列每出现一次，都会产生 (-1) ^ {k \odot T} 的贡献，这里需要将 T 看成一个二进制数（不在 T 里面的位对 (-1) ^ {p\odot z_{i, T}} 没有贡献，而 k 的等于 0 的位就算属于 T，对 (-1) ^ {p \odot z_{i, T}} 的贡献也为 1，因为 (-1) ^ {p\odot a_{i, j}} = 1，这是 k 对应的系数序列的定义）。

所以 \sum\limits_{i = 1} ^ n (-1) ^ {p \odot z_{i, T}} 也等于 \sum\limits_{k = 0} ^ {2 ^ m - 1} (-1) ^ {k \odot T} c_k。

我们发现这实际上是将 c 做 FWT 后在位置 T 的取值，因此我们只需对每个 T 均求出 H_T，则 C_i = H_{i, p}。求得 C 后 IFWT 回来即可得到 c，从而得到 [x ^ p] \prod F_i 即 [x ^ p] G，从而得到答案。

梳理一下，我们将 a_i 的每个子集（包括空集）异或起来得到 z_{i, T}，给 [x ^ {z_{i, T}}]h_T 加上 1。然后对每个 h_T 求其沃尔什变换 H_T。对于某一位置 p，H_{T, p} 的取值恰好是 d_1\sim d_m 前共 2 ^ m 种系数组合对应的出现次数序列 c 的 FWT C 在 T 处的取值。对 C IFWT 得到 c，我们因而得以求得 [x ^ p]G，最后 IFWT 即可求得 g，即答案。

时间复杂度 \mathcal{O}(nm2 ^ m + (m + k) 2 ^ {m + k})。代码如下，注意代码里面的 m 和 k 是反过来的。

#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 17, K = 1 << 3, mod = 998244353;
int ksm(int a, int b) {
    int s = 1;
    while(b) {
        if(b & 1) s = 1ll * s * a % mod;
        a = 1ll * a * a % mod, b >>= 1; // add 1ll
    }
    return s;
}
void FWT(int *f, int n, int op) {
    for(int k = 1; k < n; k <<= 1)
        for(int i = 0; i < n; i += k << 1)
            for(int j = 0, x, y; j < k; j++)
                x = f[i | j], y = f[i | j | k], f[i | j] = (x + y) % mod, f[i | j | k] = (x + mod - y) % mod;
    if(op != 1) for(int i = 0; i < n; i++) f[i] = 1ll * f[i] * op % mod;
}
int n, m, k, c[K], f[K], g[N], a[N][K], buc[K][N];
int main() {
    cin >> n >> m, k = 3;
    for(int i = 0; i < k; i++) cin >> c[i], c[i] %= mod;
    for(int i = 0; i < n; i++) {
        memset(f, 0, sizeof(f));
        for(int j = 0; j < k; j++) cin >> a[i][j];
        for(int j = 1; j < 1 << k; j++) for(int p = 0; p < k; p++) if(j >> p & 1) f[j] = f[j ^ (1 << p)] ^ a[i][p];
        for(int j = 0; j < 1 << k; j++) buc[j][f[j]]++;
    }
    for(int i = 0; i < 1 << k; i++) FWT(buc[i], 1 << m, 1);
    for(int i = 0; i < 1 << m; i++) {
        for(int j = 0; j < 1 << k; j++) f[j] = buc[j][i];
        FWT(f, 1 << k, ksm(mod + 1 >> 1, k)), g[i] = 1;
        for(int j = 0; j < 1 << k; j++) {
            int sum = 0;
            for(int p = 0; p < k; p++) sum = (sum + (j >> p & 1 ? mod - c[p] : c[p])) % mod;
            g[i] = 1ll * g[i] * ksm(sum, f[j]) % mod;
        }
    }
    FWT(g, 1 << m, ksm(mod + 1 >> 1, m));
    for(int i = 0; i < 1 << m; i++) cout << g[i] << " ";
    return 0;
}