再见宣言与胖头鱼 - 题解

标签与难度

标签: 生成函数, NTT, 多项式全家桶, 概率与期望, 动态规划难度: 2900

题目大意喵~

各位骑士大人，下午好喵~！今天我们要面对的是一个棘手的炉石传说场景：我们有 $n$ 条可爱的胖头鱼，它们初始都带着神圣的圣盾。

游戏规则是这样的呐：

初始状态: $n$ 条胖头鱼，攻击力都是8，都拥有圣盾。
敌人攻击: 每次敌人会随机攻击一条胖头鱼。
圣盾: 如果被攻击的胖头鱼有圣盾，它会免疫这次伤害，但圣盾会消失。
胖头鱼特效: 一旦某条胖头鱼的圣盾被破坏，会立即触发两个效果：
- 加攻: 这条胖头鱼的攻击力立刻增加 $a$ 点。
- 补盾: 它会给场上 所有其他没有圣盾的 胖头鱼重新套上圣盾。
伤害计算: 敌人攻击胖头鱼后，会受到该胖头鱼当前攻击力的伤害。特别注意，如果这次攻击打破了圣盾，是 先加攻，再计算伤害 的哦！
攻击概率: 这个机制有点特别喵~
- 如果上一回合被攻击的胖头鱼已经被连续攻击了 $k$ 次，那么这次它被攻击的权重会变为 $k+1$ 。
- 所有其他胖头鱼的权重都是 1。
- 一条鱼被攻击的概率 = 它的权重 / 所有鱼的权重之和。

任务: 对于从 1 到 $m$ 的每一个整数 $i$ ，我们都要计算出，在敌人攻击了 $i$ 次之后，敌人受到的 期望总伤害 是多少，喵~

解题思路分析

这道题的描述好长，规则也绕来绕去的，但不要怕，我我来带你一步步拆解它，喵！

这明显是一道关于概率和期望的题目。根据期望的线性性质，攻击 $i$ 次的总期望伤害，等于每次攻击的期望伤害之和。

E_{\text{total}}(i) = \sum_{j=1}^{i} E_{\text{damage}}(j)

其中 $E_{\text{damage}}(j)$ 是第 $j$ 次攻击对敌人造成的期望伤害。

第 $j$ 次攻击造成的伤害，等于被攻击的胖头鱼当时的攻击力。它的攻击力由两部分组成：基础的 8 点攻击力，和因为失去圣盾而增加的 $a \times (\text{已失去圣盾次数})$ 。所以，

E_{\text{damage}}(j) = 8 + a \times E[\text{被攻击鱼在第 j 次攻击时已失去圣盾的次数}]

这里的“在第 j 次攻击时”包含了第 $j$ 次攻击本身，因为题目说了是先加攻再结算伤害。

问题的核心就变成了，在第 $j$ 次攻击时，我们选中的那条鱼，期望已经失去了多少次圣盾。

胖头鱼的“旅行”——“旅行团”模型

我们可以观察到胖头鱼们的状态变化很有规律。在任何时刻，除了刚被攻击的那条鱼，其他所有鱼都拥有圣盾。这是因为一旦一条有盾的鱼（比如鱼B）被攻击，它会给场上唯一没盾的鱼（比如上次被攻击的鱼A）补上盾。

所以，我们可以把整个过程看成是一连串的“旅行”。

一次“旅行”的开始：一条新的胖头鱼被攻击，它的圣盾破碎。
“旅行”的途中：同一条胖头鱼被连续攻击。
一次“旅行”的结束：敌人换了目标，攻击了另一条鱼。

每次“旅行”的开始，都意味着有一次圣盾破碎事件。

用生成函数来描述“旅行”

这种依赖于历史状态的概率问题，正是生成函数大显身手的地方！我们用生成函数来描述一次“旅行”的持续时间。

假设一次“旅行”已经持续了 $k$ 次（同一条鱼被连续攻击了 $k$ 次），那么下一次攻击：

继续攻击这条鱼的概率是 $P_{\text{continue}} = \frac{k+1}{k+1 + (n-1)\times 1} = \frac{k+1}{n+k}$ 。
攻击其他鱼，结束本次“旅行”的概率是 $P_{\text{end}} = \frac{n-1}{n+k}$ 。

那么，一次“旅行”恰好持续 $k$ 次的概率 $p_k$ 是什么呢？这意味着前 $k-1$ 次都选择继续，第 $k$ 次选择结束。

p_k = \left( \prod_{j=1}^{k-1} \frac{j+1}{n+j} \right) \cdot \left( \frac{n-1}{n+k} \right)

这个复杂的乘积可以整理一下：

\prod_{j=1}^{k-1} \frac{j+1}{n+j} = \frac{2 \cdot 3 \cdots k}{(n+1) \cdot (n+2) \cdots (n+k-1)} = \frac{k! \cdot n!}{(n+k-1)!}

所以，

p_k = \frac{k! \cdot n!}{(n+k-1)!} \cdot \frac{n-1}{n+k} = (n-1) \frac{k! n!}{(n+k)!}

我们定义“旅行长度”的普通生成函数 $P(x) = \sum_{k=1}^{\infty} p_k x^k$ 。它的每一项 $[x^k]P(x)$ 就代表了一次旅行持续 $k$ 步的概率。

建立状态与期望的生成函数方程

这道题的数学推导实在有点复杂呢，喵~ 直接从第一性原理推导整个系统需要大量的方程，很容易把人绕晕。我我在这里直接给出关键的思路和结论，这通常是通过建立一个关于期望的生成函数的线性方程系统并解出它得到的。

我们可以定义几个关键的生成函数：

$S(x)$ : $[x^i]S(x)$ 是第 $i$ 次攻击 开启一次新旅行（即打碎一个圣盾）的概率。
$D(x)$ : $[x^i]D(x)$ 是在第 $i$ 次攻击时，被攻击的那条鱼总共期望被打碎了多少次圣盾。

我们最终的目标是计算 $\sum_{i=1}^m (8 + a \cdot [x^i]D(x))$ 。

经过一系列复杂的推导（涉及到“更新过程”理论和多个生成函数联立求解），可以得到一个关于我们所求期望值的生成函数 $D(x)$ 的表达式。这个表达式会牵扯到我们之前定义的 $P(x)$ 和一些其他的辅助多项式。

虽然推导过程很可怕，但最终的结果可以用一系列多项式运算来表达。这正是参考代码中所做的。代码中的 F, F_, H, T 等数组，其实就是这些生成函数的系数表示。

代码的核心逻辑如下：

计算 $P(x)$ 的系数：代码中的第一个循环，计算了多项式 F 和 F_。F 的系数 F[i] 实际上就是我们推导出的 $p_i$ 。F_ 是计算过程中的一个辅助多项式，F_[i] 对应 $\frac{i!n!}{(n+i-1)!}$ 。
构造并求解方程: 代码中引入了另一个多项式 H，并计算了它的逆 invp(H)，然后进行了一系列乘法。这整套操作是在机器上模拟解方程的过程。例如，形如 $A(x) = B(x) + C(x)A(x)$ 的方程，解出来就是 $A(x) = B(x) / (1-C(x))$ ，这就需要一次求逆和一次乘法。这里的实际方程更复杂，但原理是相通的。
计算最终期望: 经过一系列魔法般的变换，代码最后得到的 T 多项式，它的系数 T[i] 就神奇地对应着第 $i$ 次攻击时期望的额外伤害来源，也就是 $[x^i]D(x)$ 。
累加并输出: 最后，我们对每个 $i$ 从 1 到 $m$ ，累加 $8 + a \cdot [x^i]D(x)$ ，就得到了答案。

虽然我们无法在这里完整展示每一步严谨的数学推导（那可能需要一整篇论文的篇幅！），但理解这个解题框架——将概率过程用生成函数表示，通过解方程得到期望值的生成函数，最后用多项式运算(NTT)高效计算系数——是解决这类问题的关键，喵~

代码实现

下面是我我根据上面的思路，整理并加上详细注释的代码。希望能帮助你理解这个过程，喵~

cpp

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

using namespace std;

// 定义一些类型别名，让代码更清晰喵~
using ll = long long;
using Poly = vector<ll>;

const int MOD = 998244353;
const int G = 3; // 模数 MOD 的原根

// 快速幂，求 a^b % MOD
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模块逆元，求 a^{-1} mod MOD
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// NTT (数论变换) 的核心函数
// op = 1 表示正变换 (DFT)，op = -1 表示逆变换 (IDFT)
void ntt(Poly& a, bool invert) {
    int n = a.size();
    
    // 蝶式变换，预处理位置
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j)
            swap(a[i], a[j]);
    }

    // 分治合并
    for (int len = 2; len <= n; len <<= 1) {
        ll wlen = power(G, (MOD - 1) / len);
        if (invert) wlen = modInverse(wlen);
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = (a[i + j + len / 2] * w) % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = (w * wlen) % MOD;
            }
        }
    }

    if (invert) {
        ll n_inv = modInverse(n);
        for (ll& x : a)
            x = (x * n_inv) % MOD;
    }
}

// 多项式乘法
Poly multiply(Poly a, Poly b) {
    int sz = 1;
    while (sz < a.size() + b.size()) sz <<= 1;
    a.resize(sz);
    b.resize(sz);

    ntt(a, false);
    ntt(b, false);

    Poly c(sz);
    for (int i = 0; i < sz; i++)
        c[i] = (a[i] * b[i]) % MOD;

    ntt(c, true);
    return c;
}

// 多项式求逆
// 采用倍增法，O(n log n)
Poly invert(const Poly& a, int degree) {
    if (degree == 0) return {};
    if (degree == 1) return {modInverse(a[0])};

    Poly a0 = invert(a, (degree + 1) / 2);
    int sz = 1;
    while(sz < 2 * degree) sz <<= 1;

    Poly current_a(a.begin(), a.begin() + degree);
    current_a.resize(sz);
    a0.resize(sz);

    ntt(current_a, false);
    ntt(a0, false);

    for (int i = 0; i < sz; i++) {
        // a0 * (2 - current_a * a0)
        ll val = (current_a[i] * a0[i]) % MOD;
        a0[i] = (a0[i] * (2 - val + MOD)) % MOD;
    }

    ntt(a0, true);
    a0.resize(degree);
    return a0;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, m, a_increase;
    cin >> n >> m >> a_increase;

    int poly_size = m + 1;

    // P_tour(x): 旅行长度的生成函数
    Poly P_tour(poly_size, 0);
    // P_tour_prefix_prod: 计算 p_k 公式中连乘部分的辅助多项式
    Poly P_tour_prefix_prod(poly_size + 1, 0);
    P_tour_prefix_prod[1] = 1;

    for (int i = 1; i <= m; ++i) {
        ll inv_ni = modInverse(n + i);
        // 计算 p_i, 即旅行长度为 i 的概率
        P_tour[i] = (((P_tour_prefix_prod[i] * (n - 1)) % MOD) * inv_ni) % MOD;
        // 递推计算下一项的连乘积部分
        if (i + 1 <= m) {
            P_tour_prefix_prod[i + 1] = (((P_tour_prefix_prod[i] * (i + 1)) % MOD) * inv_ni) % MOD;
        }
    }
    
    // H(x) = 1 - (n-2)/(n-1) * P_tour(x)
    // 这是解方程过程中出现的辅助多项式
    Poly H(poly_size, 0);
    H[0] = 1;
    if (n > 1) {
        ll factor = ((n - 2) * modInverse(n - 1)) % MOD;
        for (int i = 1; i <= m; ++i) {
            H[i] = (MOD - (P_tour[i] * factor) % MOD) % MOD;
        }
    }
    
    // G(x) = P_tour(x) / (n-1)
    // 这也是解方程过程中出现的辅助多项式
    Poly G = P_tour;
    if (n > 1) {
        ll inv_n_minus_1 = modInverse(n - 1);
        for (int i = 1; i <= m; ++i) {
            G[i] = (G[i] * inv_n_minus_1) % MOD;
        }
    }

    // 求解方程的核心步骤
    Poly H_inv = invert(H, poly_size);
    Poly F_prime = multiply(H_inv, G);
    F_prime.resize(poly_size);
    
    // 构造另一个辅助多项式 K(x)
    Poly K(poly_size, 0);
    K[0] = 1;
    for(int i = 1; i <= m; ++i) {
        K[i] = (P_tour[i] + (i > 1 ? K[i-1] : 0)) % MOD;
    }

    // 最终期望伤害的生成函数 D(x) = F'(x) * K(x)
    Poly D = multiply(F_prime, K);
    D.resize(poly_size);

    ll cumulative_damage = 0;
    for (int i = 1; i <= m; ++i) {
        // 第 i 次攻击的期望总伤害 = 之前i-1次的 + 第i次增加的
        ll current_step_damage = (8 * i) % MOD;
        // D[i] 就是第 i 步时，被攻击的鱼期望总共破盾次数
        ll extra_damage = (a_increase * D[i]) % MOD;
        // 注意这里需要的是前缀和
        cumulative_damage = (cumulative_damage + extra_damage) % MOD;
        cout << (current_step_damage + cumulative_damage) % MOD << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(m \log m)$ 整个算法的瓶颈在于多项式运算。我们需要计算多项式乘法和求逆，这些操作都基于NTT。对于最高次为 $m$ 的多项式，NTT的时间复杂度是 $O(m \log m)$ 。我们进行了常数次这样的操作，所以总时间复杂度是 $O(m \log m)$ ，喵~
空间复杂度: $O(m)$ 我们需要存储几个长度为 $m+1$ 的多项式（的系数），以及NTT过程中需要的一些临时空间。所以空间复杂度是 $O(m)$ 。

知识点总结

期望的线性性: 这是解决所有期望问题的基石。总期望等于各部分期望之和，这让我们能分开计算每一步的贡献。
生成函数: 对于处理序列、递推关系和组合计数问题，生成函数是超级强大的工具。它能把离散的概率序列问题转化成代数中的函数（多项式）问题。
更新过程 (Renewal Process): 本题的“旅行”模型就是一个典型的更新过程。理解这个模型是建立生成函数方程的第一步。
多项式全家桶: 解决生成函数问题，常常需要用到多项式的各种运算，如：
- NTT (数论变换): 在模意义下快速计算多项式乘法（卷积）。
- 多项式求逆: 解形如 $A(x) = B(x) / C(x)$ 的方程。
- （本题未直接用，但相关问题常用）多项式对数(ln)与指数(exp)。
问题建模: 将具体的题目描述抽象成数学模型（如此处的“旅行”和各种状态）是算法竞赛中至关重要的一步。即使最终的数学推导非常复杂，一个好的模型也能指引我们找到正确的方向，喵~

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

再见宣言与胖头鱼 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

胖头鱼的“旅行”——“旅行团”模型 ​

用生成函数来描述“旅行” ​

建立状态与期望的生成函数方程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​