「ZJOI2020」抽卡 题解

算法思路分析

这是一个期望抽卡次数计算问题，需要用到生成函数、多项式运算和容斥原理。

问题转化

设 $E$ 为期望抽卡次数，根据期望的线性性，可以转化为：

$$E = \sum_{i=0}^{\infty} P(\text{前} i \text{轮未结束})$$

关键观察

1. 停止条件：当收集到任意一个长度为 $k$ 的连续区间时停止
2. 容斥原理：计算不包含任何长度为 $k$ 的连续区间的概率
3. 生成函数：用多项式表示状态转移概率

核心算法组件

1. 多项式运算 (Poly 命名空间)

namespace Poly {
    void NTT(int *s, CI op);  // 快速数论变换
    void Mul(CI n, int *a, int *b);  // 多项式乘法
    void Inv(CI n, int *a, int *b);  // 多项式求逆
    void Ln(CI n, int *a, int *b);   // 多项式对数
    void Exp(CI n, int *a, int *b);  // 多项式指数
    void Pow(CI n, int *a, CI k);    // 多项式快速幂
}

2. 牛顿迭代求解

void Newton(CI n, int *f) {
    // 使用牛顿迭代法求解关键生成函数
    // 涉及多项式求逆、乘法、快速幂等操作
}

3. 分治 NTT

void Solve(CI l, CI r) {
    // 分治策略计算多个连续段的生成函数乘积
    if (l == r) return;
    RI mid = l + r >> 1;
    Solve(l, mid), Solve(mid + 1, r);
    Mul(F[l], F[mid + 1]);
}

算法步骤

步骤 1：预处理

• 排序卡牌编号
• 预处理阶乘和逆元用于组合数计算
• 调用 Newton 迭代计算基础生成函数

步骤 2：处理连续段

// 找出所有极长连续段
for (i = 2; i <= n + 1; ++i)
    a[i]^(a[i-1]+1) && (s[++c] = t, t = 0), ++t;

步骤 3：计算每个连续段的生成函数

for (i = 1; i <= c; ++i) {
    Poly::Pow(s[i], ff, s[i] + 1);  // 多项式快速幂
    // 计算该段的贡献生成函数
    for (j = 1; j <= s[i]; ++j)
        F[i].push_back(1LL * (s[i]-j+1)*ff[j] % X * v % X);
}

步骤 4：合并所有段的生成函数

Poly::Solve(1, c);  // 分治NTT合并所有生成函数

步骤 5：计算最终期望

for (i = 0; i ^ n; ++i)
    ans = (1LL * F[1][i] * n % X * QP(n-i, X-2) % X * IC(n,i) + ans) % X;

复杂度分析

• 时间复杂度：$O(n \log^2 n)$，主要来自多项式运算和分治NTT
• 空间复杂度：$O(n)$，存储多项式和中间结果

算法标签

主要分类

• 生成函数 ⭐⭐⭐⭐⭐
• 多项式运算 ⭐⭐⭐⭐⭐
• 期望概率 ⭐⭐⭐⭐

技术子标签

• 快速数论变换 (NTT) ⭐⭐⭐⭐
• 容斥原理 ⭐⭐⭐⭐
• 牛顿迭代 ⭐⭐⭐⭐
• 分治算法 ⭐⭐⭐

数学工具

• 组合数学 ⭐⭐⭐⭐
• 模运算 ⭐⭐⭐⭐

关键公式推导

期望计算公式

$$E = \sum_{i=0}^{n} \frac{n}{n-i} \cdot \frac{1}{\binom{n}{i}} \cdot F(i) $$

其中 $F(i)$ 表示选择 $i$ 张卡且不包含任何长度为 $k$ 的连续区间的方案数。

生成函数关系

设 $f(x)$ 为答案的生成函数，通过牛顿迭代求解：

$$f(x) = \frac{1 - x - x^2}{1 - (k+1)x^k}$$

算法创新点

1. 生成函数建模：将组合计数问题转化为多项式运算
2. 牛顿迭代：高效求解生成函数方程
3. 分治NTT：处理多个连续段的生成函数乘积
4. 容斥原理：排除包含连续区间的情况

该解法通过生成函数和多项式技术的深度应用，成功解决了大规模抽卡期望计算问题，展现了现代组合数学在算法竞赛中的强大威力。