lonely - 题解

标签与难度

标签: 快速沃尔什变换(FWT), 子集卷积, 生成函数, 动态规划, 组合数学难度: 2500

题目大意喵~

你好呀，指挥官！这道题是要我们计算一些和集合划分有关的奇妙数值，喵~

我们有 $n$ 个点，从 $0$ 到 $n-1$ 编号。对于 $2^n - 1$ 个非空点集 $S$ ，我们有两个给定的数组：权值 $a_S$ 和贡献值 $b_S$ 。

接着，题目定义了一个函数 $f_{S, i}$ ，它表示将集合 $S$ 划分成 $i$ 个非空、互不相交的子集的所有方案中，每个方案的权值之积的总和。举个例子，如果把 $S$ 划分成 $T_1, T_2, \dots, T_i$ （其中 $T_j \neq \emptyset$ , $T_j \cap T_k = \emptyset$ , $\cup_{j=1}^i T_j = S$ ），那么这个划分方案的权值就是 $a_{T_1} \times a_{T_2} \times \dots \times a_{T_i}$ 。 $f_{S,i}$ 就是所有这些不同划分方案的权值加起来的总和。

我们的最终任务是，对于每个 $i$ (从 $1$ 到 $n$ )，计算出下面这个式子的值：

\text{Ans}_i = \sum_{S \subseteq U, S \neq \emptyset} b_S \cdot f_{S, i}

其中 $U$ 是包含所有 $n$ 个点的全集。所有计算都要在模 $998244353$ 下进行。

解题思路分析

这道题看起来好复杂，又是集合划分又是求和的，但别怕，我我来带你一步步解开它的神秘面纱，喵~

核心问题：集合划分与子集卷积

首先，我们来仔细看看 $f_{S,i}$ 的定义。它是在对集合 $S$ 进行划分。这种对集合进行划分并求权值乘积和的形式，是一个非常典型的组合结构，通常和子集卷积以及生成函数有关。

让我们定义一种运算，叫做子集卷积，记作 *。对于两个关于子集的函数 $A$ 和 $B$ ，它们的子集卷积 $C = A * B$ 定义为：

C_S = \sum_{T \subseteq S} A_T \cdot B_{S \setminus T}

这个式子计算了所有将集合 $S$ 分成两部分 $T$ 和 $S \setminus T$ 的方案，并将两部分的函数值乘起来再求和。

现在回到 $f_{S,i}$ 。

当 $i=1$ 时，只有一种划分方法，就是 $S$ 本身。所以 $f_{S,1} = a_S$ 。
当 $i=2$ 时，我们需要把 $S$ 分成两个非空子集 $T_1$ 和 $T_2$ 。这和子集卷积很像！ $f_{S,2}$ 是所有 $a_{T_1} \cdot a_{T_2}$ 的和。如果我们计算 $(a*a)_S = \sum_{T \subseteq S} a_T a_{S \setminus T}$ ，会发现每个无序对 $\{T_1, T_2\}$ 被计算了两次（一次是 $T=T_1$ ，一次是 $T=T_2$ ）。所以 $f_{S,2} = \frac{1}{2}(a*a)_S$ 。
推广开来，如果我们定义 $a^{*i}$ 为 $a$ 与自身进行 $i$ 次子集卷积，那么 $f_{S,i}$ 就是 $a^{*i}$ 中 $S$ 对应的系数，再除以 $i!$ （因为 $i$ 个集合的划分是无序的）。

所以，我们可以把 $f_{*,i}$ （表示所有 $f_{S,i}$ 构成的数组）看作是 $a$ 数组的某种 "指数" 运算的结果。

f_{*, i} = \frac{1}{i!} a^{*i}

引入快速沃尔什变换 (FWT)

直接计算子集卷积非常慢，复杂度高达 $O(3^n)$ 。而要计算 $i$ 次方，总复杂度会是 $O(n \cdot 3^n)$ 或者使用快速幂优化到 $O(\log i \cdot 3^n)$ ，对于 $n=20$ 来说是绝对无法接受的。

但是，对于一类特殊的卷积——子集和卷积（OR卷积）、子集交卷积（AND卷积）和子集异或卷积（XOR卷积），我们可以使用一种叫快速沃尔什变换 (FWT) 的算法，在 $O(n 2^n)$ 的时间内完成。

虽然子集卷积本身不能直接用 FWT 加速，但它和 FWT 有着深刻的联系。一个关键的性质是，我们可以利用 FWT（这里特指子集和变换，也叫 Zeta 变换或 SOS DP）来简化问题。

我们定义一个数组 $A$ 的 FWT（子集和变换）为 $\hat{A}$ ，其中：

\hat{A}_S = \sum_{T \subseteq S} A_T

这个变换是线性的，并且有一个神奇的性质：它能将一些复杂的集合运算转化为简单的逐点运算。对于集合划分问题，有这样一个美妙的结论：

令 $\hat{f}_{M,i} = \sum_{S \subseteq M} f_{S,i}$ 和 $\hat{a}_M = \sum_{S \subseteq M} a_S$ 。那么它们之间满足：

\sum_{i=0}^{\infty} \hat{f}_{M,i} y^i = \exp(y \cdot \hat{a}_M) = \sum_{i=0}^{\infty} \frac{(\hat{a}_M)^i}{i!} y^i

比较等式两边 $y^i$ 的系数，我们得到一个超级重要的关系！

\hat{f}_{M,i} = \frac{(\hat{a}_M)^i}{i!}

这意味着，只要我们对 $a$ 数组做一次 FWT 得到 $\hat{a}$ ，我们就可以轻松地在变换域中得到 $\hat{f}_{*,i}$ ，而不需要进行任何昂贵的子集卷积！

求解最终答案

我们的目标是计算 $\text{Ans}_i = \sum_S b_S f_{S,i}$ 。这是一个点积的形式。我们已经知道了 $\hat{f}_{*,i}$ ，但如何利用它来求和呢？直接对 $\hat{f}_{*,i}$ 做逆 FWT 得到 $f_{S,i}$ 再求和，复杂度又回去了。

这里需要一个关于 FWT 的求和恒等式。对于两个数组 $X$ 和 $Y$ ，它们的点积满足：

\sum_{S \subseteq U} X_S Y_S = \sum_{S \subseteq U} (-1)^{|S|} \hat{X}_S \check{Y}_{U \setminus S}

其中 $U$ 是全集， $\hat{X}$ 是 $X$ 的子集和变换（Sum over Subsets），而 $\check{Y}$ 是 $Y$ 的超集和变换（Sum over Supermasks）。

\hat{X}_S = \sum_{T \subseteq S} X_T

\check{Y}_S = \sum_{T \supseteq S} Y_T

这两种变换都可以用 FWT 在 $O(n 2^n)$ 的时间内计算出来。

把这个恒等式应用到我们的问题上，令 $X=b$ ， $Y=f_{*,i}$ ：

\text{Ans}_i = \sum_{S \subseteq U} b_S f_{S,i} = \sum_{S \subseteq U} (-1)^{|S|} \hat{b}_S \check{f}_{U \setminus S, i}

现在的问题是， $\check{f}_{M,i}$ 是什么？奇迹再次发生！超集和变换与子集划分也有着类似的美妙关系：

\check{f}_{M,i} = \frac{(\check{a}_M)^i}{i!}

其中 $\check{a}_M = \sum_{T \supseteq M} a_T$ 。

把这个代入我们的答案公式中，就得到了最终的计算方法！

\text{Ans}_i = \sum_{S \subseteq U} (-1)^{|S|} \hat{b}_S \frac{(\check{a}_{U \setminus S})^i}{i!}

\text{Ans}_i = \frac{1}{i!} \sum_{S \subseteq U} (-1)^{|S|} (\sum_{T \subseteq S} b_T) \cdot (\sum_{T' \supseteq U \setminus S} a_{T'})^i

这个公式看起来吓人，但它告诉我们一个清晰的算法步骤：

对数组 $b$ 进行子集和 FWT，得到 $\hat{b}$ 。
对数组 $a$ 进行超集和 FWT，得到 $\check{a}$ 。
预计算阶乘的逆元 $1/i!$ 。
对于每个 $i=1, \dots, n$ ，遍历所有子集 $S$ ，累加 (-1)^|S| * hat_b[S] * (check_a[U \ S])^i。
最后将累加和乘以 $1/i!$ 就是 $\text{Ans}_i$ 。

整个算法的瓶颈在于两次 FWT 和最后的求和循环，总时间复杂度为 $O(n 2^n)$ ，对于 $n=20$ 来说完全可以接受，喵~

代码实现

下面就是我根据上面的思路，精心为你准备的代码啦！注释写得很详细，希望能帮助你理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 定义模数
const int MOD = 998244353;
const int MAXN = 20;

// 快速幂，用于计算逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 快速沃尔什变换 - 子集和 (SOS DP)
// in-place 实现，op=1 为正变换，op=-1 为逆变换
void FWT_SOS(vector<long long>& a, int n, int op) {
    int size = 1 << n;
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < size; ++mask) {
            if (mask & (1 << i)) {
                long long term = a[mask ^ (1 << i)];
                if (op == 1) {
                    a[mask] = (a[mask] + term) % MOD;
                } else {
                    a[mask] = (a[mask] - term + MOD) % MOD;
                }
            }
        }
    }
}

// 快速沃尔什变换 - 超集和
// in-place 实现, op=1 为正变换, op=-1 为逆变换
void FWT_Supermask(vector<long long>& a, int n, int op) {
    int size = 1 << n;
    for (int i = 0; i < n; ++i) {
        for (int mask = size - 1; mask >= 0; --mask) {
            if (mask & (1 << i)) {
                long long term = a[mask ^ (1 << i)];
                if (op == 1) {
                    a[mask] = (a[mask] + term) % MOD;
                } else {
                    a[mask] = (a[mask] - term + MOD) % MOD;
                }
            }
        }
    }
}


int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int size = 1 << n;
    vector<long long> a(size, 0), b(size, 0);

    // 读入 a_S，下标 S > 0
    for (int i = 1; i < size; ++i) {
        cin >> a[i];
    }
    // 读入 b_S，下标 S > 0
    for (int i = 1; i < size; ++i) {
        cin >> b[i];
    }

    // 预计算阶乘和它们的逆元
    vector<long long> inv_fact(n + 1);
    vector<long long> fact(n + 1);
    fact[0] = 1;
    inv_fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        inv_fact[i] = power(fact[i], MOD - 2);
    }

    // 1. 对 b 进行子集和 FWT
    vector<long long> hat_b = b;
    FWT_SOS(hat_b, n, 1);

    // 2. 对 a 进行超集和 FWT
    vector<long long> check_a = a;
    // 注意！超集和变换等价于对 bit-reversed 的数组做子集和变换
    // 或者直接写超集和的循环，这里为了清晰就直接写了
    FWT_Supermask(check_a, n, 1);

    // 3. 计算最终答案
    vector<long long> ans(n + 1, 0);
    int full_mask = size - 1;

    // 为了效率，我们交换内外循环
    // 外层循环遍历 S，内层循环计算对所有 Ans_i 的贡献
    for (int s = 0; s < size; ++s) {
        long long b_term = hat_b[s];
        if (__builtin_popcount(s) % 2 != 0) {
            b_term = (MOD - b_term) % MOD;
        }

        long long a_term_base = check_a[full_mask ^ s];
        long long a_power = 1;

        for (int i = 1; i <= n; ++i) {
            a_power = (a_power * a_term_base) % MOD;
            long long contribution = (b_term * a_power) % MOD;
            ans[i] = (ans[i] + contribution) % MOD;
        }
    }

    // 4. 乘以 1/i!
    for (int i = 1; i <= n; ++i) {
        ans[i] = (ans[i] * inv_fact[i]) % MOD;
    }

    // 5. 输出结果
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \cdot 2^N)$ ，其中 $N$ 是点的数量。
- 两次 FWT (子集和与超集和) 的复杂度都是 $O(N \cdot 2^N)$ 。
- 预计算阶乘逆元是 $O(N \log \text{MOD})$ 。
- 最后计算答案的循环，外层是 $2^N$ 次，内层是 $N$ 次，所以也是 $O(N \cdot 2^N)$ 。
- 因此总时间复杂度由 FWT 和求和部分主导，为 $O(N \cdot 2^N)$ 。
空间复杂度: $O(2^N)$ 。
- 我们需要存储 a, b 数组以及它们的变换结果，每个数组的大小都是 $2^N$ 。所以空间复杂度是 $O(2^N)$ 。

知识点总结

这道题是集合动态规划问题中的一个经典模型，融合了多个重要的算法思想，很值得好好回味一下，喵~

集合划分与生成函数: 问题的核心是集合划分，这种组合结构通常可以和指数型生成函数联系起来。f_{S,i} 的形式就是多项式指数函数的系数。
子集卷积: 集合划分的递推关系天然地形成了子集卷积的形式。虽然我们最终没有直接计算它，但理解这个概念是找到正确方向的第一步。
快速沃尔什变换 (FWT): FWT 是解决各类子集相关卷积问题的利器。本题中，我们利用了 FWT 的两个变种：
- 子集和变换 (Zeta Transform / SOS DP): $\hat{A}_S = \sum_{T \subseteq S} A_T$
- 超集和变换 (Dual Zeta Transform): $\check{A}_S = \sum_{T \supseteq S} A_T$
FWT 与集合运算的关系: 最关键的知识点！FWT 可以将复杂的集合运算（如子集卷积的指数运算）转化为变换域中简单的逐点运算。我们利用了 $\hat{f}_{M,i} = (\hat{a}_M)^i/i!$ 和 $\check{f}_{M,i} = (\check{a}_M)^i/i!$ 这两个核心性质。
求和恒等式: 为了在变换域中计算点积，我们使用了一个优美的恒等式 $\sum X_S Y_S = \sum (-1)^{|S|} \hat{X}_S \check{Y}_{U \setminus S}$ ，它将两个不同类型的 FWT 巧妙地联系在了一起，避免了代价高昂的逆变换。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦，喵~！

lonely - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心问题：集合划分与子集卷积 ​

引入快速沃尔什变换 (FWT) ​

求解最终答案 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​