Easy - 题解

标签与难度

标签: 组合数学, 生成函数, 计数问题, 隔板法, 快速幂 难度: 2100

题目大意喵~

主人，你好呀~！这道题目是这样的喵：

我们要和 Mr. W 一起玩序列游戏！他会写下两个长度都为 $K$ 的正整数序列 $A = (a_1, a_2, \dots, a_K)$ 和 $B = (b_1, b_2, \dots, b_K)$。

这两个序列需要满足两个条件：

1. 序列 $A$ 的所有元素之和为 $N$，也就是 $\sum_{i=1}^{K} a_i = N$。
2. 序列 $B$ 的所有元素之和为 $M$，也就是 $\sum_{i=1}^{K} b_i = M$。

对于每一对满足条件的序列 $(A, B)$，Mr. W 会得到一个分数 $P = \prod_{i=1}^K \min(a_i, b_i)$。

我们的任务是，计算出对于所有可能的序列对 $(A, B)$，他能获得的总分数是多少呢？因为答案可能很大，所以要对 $998244353$ 取模哦，喵~

解题思路分析

这道题看起来有点吓人呢，又是求和又是求积的，直接去枚举所有可能的序列 $A$ 和 $B$ 肯定是不行的啦，会累坏的，喵~ (ΦωΦ)

当遇到这种复杂的计数问题，特别是混合了加法和乘法的时候，我的直觉告诉我，生成函数这个强大的魔法工具可能要登场啦！

构造生成函数

让我们先只考虑序列中的一个位置 $i$。对于这一对数字 $(a_i, b_i)$，它们对分数的贡献是 $\min(a_i, b_i)$。我们可以为这一对数字构造一个二维生成函数 $G(x, y)$，其中 $x$ 的指数对应 $a_i$ 的值，$y$ 的指数对应 $b_i$ 的值，而系数就是它们的得分 $\min(a_i, b_i)$。

$$G(x, y) = \sum_{a=1}^{\infty} \sum_{b=1}^{\infty} \min(a, b) x^a y^b$$

这个式子看起来有点复杂，我们来化简它。我们可以按照 $\min(a, b)$ 的值 $c$ 来分类讨论：

$$G(x, y) = \sum_{c=1}^{\infty} c \left( \sum_{\substack{a \ge c, b=c}} x^a y^b + \sum_{\substack{a=c, b > c}} x^a y^b \right)$$

这个式子我好像写错了呢，应该是：

$$G(x, y) = \sum_{c=1}^{\infty} c \left( x^c y^c + x^c \sum_{b=c+1}^{\infty} y^b + y^c \sum_{a=c+1}^{\infty} x^a \right)$$

这里的第一项 $x^c y^c$ 对应 $a=c, b=c$ 的情况。第二项对应 $a=c, b > c$ 的情况。第三项对应 $b=c, a > c$ 的情况。 把它们加起来，就是所有 $\min(a,b)=c$ 的情况啦。

使用等比数列求和公式 $\sum_{k=n}^{\infty} r^k = \frac{r^n}{1-r}$（当 $|r|<1$ 时），我们得到：

$$\sum_{b=c+1}^{\infty} y^b = \frac{y^{c+1}}{1-y} \quad \text{和} \quad \sum_{a=c+1}^{\infty} x^a = \frac{x^{c+1}}{1-x}$$

代入 $G(x, y)$ 的表达式中：

$$\begin{aligned} G(x, y) &= \sum_{c=1}^{\infty} c \left( x^c y^c + x^c \frac{y^{c+1}}{1-y} + y^c \frac{x^{c+1}}{1-x} \right) \\ &= \sum_{c=1}^{\infty} c (xy)^c \left( 1 + \frac{y}{1-y} + \frac{x}{1-x} \right) \\ &= \left( \frac{(1-x)(1-y) + y(1-x) + x(1-y)}{(1-x)(1-y)} \right) \sum_{c=1}^{\infty} c (xy)^c \\ &= \left( \frac{1-x-y+xy + y-xy + x-xy}{(1-x)(1-y)} \right) \sum_{c=1}^{\infty} c (xy)^c \\ &= \frac{1-xy}{(1-x)(1-y)} \sum_{c=1}^{\infty} c (xy)^c \end{aligned}$$

对于 $\sum_{c=1}^{\infty} c z^c$ 这个级数，它等于 $\frac{z}{(1-z)^2}$。所以，令 $z=xy$：

$$G(x, y) = \frac{1-xy}{(1-x)(1-y)} \cdot \frac{xy}{(1-xy)^2} = \frac{xy}{(1-x)(1-y)(1-xy)}$$

喵~ 看，我们得到了一个非常简洁漂亮的封闭形式！

求解总分数

我们有两个长度为 $K$ 的序列，每个位置 $(a_i, b_i)$ 都是独立的（除了总和的限制），所以总的生成函数就是 $K$ 个 $G(x, y)$ 相乘：

$$\mathcal{G}(x, y) = [G(x, y)]^K = \left( \frac{xy}{(1-x)(1-y)(1-xy)} \right)^K$$

我们要求的总分数，就是这个总生成函数 $\mathcal{G}(x, y)$ 中 $x^N y^M$ 项的系数，记作 $[x^N y^M]\mathcal{G}(x, y)$。

$$[x^N y^M] \frac{x^K y^K}{(1-x)^K (1-y)^K (1-xy)^K}$$

这等价于求下面这个表达式中 $x^{N-K} y^{M-K}$ 项的系数：

$$[x^{N-K} y^{M-K}] \frac{1}{(1-x)^K (1-y)^K (1-xy)^K}$$

为了求这个系数，我们要用到广义二项式定理：

$$(1-z)^{-k} = \sum_{i=0}^{\infty} \binom{-k}{i} (-z)^i = \sum_{i=0}^{\infty} \binom{k+i-1}{i} z^i$$

这是一个非常有用的公式，主人要记住哦！

现在我们把三个分式展开：

• $(1-x)^{-K} = \sum_{j=0}^{\infty} \binom{K+j-1}{j} x^j$
• $(1-y)^{-K} = \sum_{l=0}^{\infty} \binom{K+l-1}{l} y^l$
• $(1-xy)^{-K} = \sum_{s=0}^{\infty} \binom{K+s-1}{s} (xy)^s = \sum_{s=0}^{\infty} \binom{K+s-1}{s} x^s y^s$

我们将这三个级数相乘，要凑出 $x^{N-K} y^{M-K}$ 项。这意味着我们需要找到所有满足 $j+s = N-K$ 和 $l+s = M-K$ 的非负整数 $j, l, s$。

对于一个固定的 $s$，我们必须取 $j = N-K-s$ 和 $l = M-K-s$。 此时，对答案的贡献是这三项系数的乘积：

$$\binom{K+(N-K-s)-1}{N-K-s} \cdot \binom{K+(M-K-s)-1}{M-K-s} \cdot \binom{K+s-1}{s}$$

整理一下组合数：

$$\binom{N-s-1}{N-K-s} \cdot \binom{M-s-1}{M-K-s} \cdot \binom{K+s-1}{s}$$

再利用组合数的对称性 $\binom{n}{k} = \binom{n}{n-k}$：

$$\binom{N-s-1}{K-1} \cdot \binom{M-s-1}{K-1} \cdot \binom{K+s-1}{s}$$

最后，我们对所有可能的 $s$ 求和。$s$ 的取值范围是什么呢？因为 $j, l, s$ 都必须是非负数，所以 $N-K-s \ge 0 \implies s \le N-K$ 且 $M-K-s \ge 0 \implies s \le M-K$。所以 $s$ 的取值范围是 $0 \le s \le \min(N-K, M-K)$。

于是，我们得到了最终的求和公式！

$$\text{总分数} = \sum_{s=0}^{\min(N-K, M-K)} \binom{K+s-1}{s} \binom{N-s-1}{K-1} \binom{M-s-1}{K-1} \pmod{998244353}$$

实现细节

要实现这个公式，我们需要：

1. 预处理阶乘和阶乘逆元：为了快速计算组合数 $\binom{n}{k} = \frac{n!}{k!(n-k)!} \pmod p$，我们可以预先计算出一定范围内所有数的阶乘 fact[i] 和阶乘的模逆元 infact[i]。
2. 快速幂：计算模逆元需要用到快速幂，根据费马小定理，$a^{p-2} \equiv a^{-1} \pmod p$（当 $p$ 是质数时）。
3. 循环求和：按照上面的公式，写一个循环从 $s=0$ 到 $\min(N-K, M-K)$，累加每一项的值就可以啦。

好啦，思路清晰了，我要开始写代码啦！ฅ^•ﻌ•^ฅ

代码实现

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

// 使用 long long 防止中间计算溢出，喵~
using int64 = long long;

const int MOD = 998244353;
const int MAX_SIZE = 1000000 + 10; // 题目数据范围 N, M <= 10^6

// 预处理阶乘和阶乘的逆元
std::vector<int64> fact(MAX_SIZE);
std::vector<int64> inv_fact(MAX_SIZE);

// 快速幂函数，用来求模逆元
int64 power(int64 base, int64 exp) {
    int64 res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 求模逆元
int64 mod_inverse(int64 n) {
    return power(n, MOD - 2);
}

// 预处理阶乘和逆阶乘的函数
void precompute_factorials() {
    fact[0] = 1;
    inv_fact[0] = 1;
    for (int i = 1; i < MAX_SIZE; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    inv_fact[MAX_SIZE - 1] = mod_inverse(fact[MAX_SIZE - 1]);
    for (int i = MAX_SIZE - 2; i >= 1; --i) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

// 计算组合数的函数 C(n, k)
int64 combinations(int n, int k) {
    if (k < 0 || k > n) {
        return 0; // k 不合法，返回0种方案
    }
    return (((fact[n] * inv_fact[k]) % MOD) * inv_fact[n - k]) % MOD;
}

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    
    // a_i 和 b_i 都是正整数，所以 N, M 必须至少是 K
    if (n < k || m < k) {
        std::cout << 0 << "\n";
        return;
    }

    int64 total_score = 0;
    int upper_bound = std::min(n - k, m - k);

    // 循环变量 s 对应我们推导出的公式中的 s
    for (int s = 0; s <= upper_bound; ++s) {
        int64 term1 = combinations(k + s - 1, s);
        int64 term2 = combinations(n - s - 1, k - 1);
        int64 term3 = combinations(m - s - 1, k - 1);
        
        int64 current_term = (term1 * term2) % MOD;
        current_term = (current_term * term3) % MOD;
        
        total_score = (total_score + current_term) % MOD;
    }
    
    std::cout << total_score << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    precompute_factorials();

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(\text{MAX\_SIZE} + T \cdot \min(N, M))$

  • precompute_factorials() 函数需要 $O(\text{MAX\_SIZE})$ 的时间来计算阶乘和逆阶乘，其中 MAX_SIZE 是 $N, M, K$ 的最大可能值。
  • 对于每组测试数据，我们需要一个循环来计算总和。循环的次数是 $\min(N-K, M-K) + 1$，所以这部分的复杂度是 $O(\min(N, M))$。
  • 因此，总的时间复杂度是预处理加上所有测试用例的计算时间。

• 空间复杂度: $O(\text{MAX\_SIZE})$

  • 我们需要两个数组 fact 和 inv_fact 来存储预计算的结果，每个数组的大小都是 MAX_SIZE。

知识点总结

这道题虽然名字叫 "Easy"，但其实一点也不 "Easy" 呢，哼哼~ 它考察了我们很多重要的知识点：

1. 生成函数: 它是解决复杂组合计数问题的终极武器之一！通过将组合问题转化为代数问题（多项式/级数的运算），可以大大简化问题。
2. 组合数学: 核心是组合数 $\binom{n}{k}$ 的计算和其性质的应用，比如广义二项式定理。
3. 模运算: 在算法竞赛中，当结果很大时，模运算是家常便饭。我们需要熟悉模加法、模乘法以及如何求模逆元。
4. 费马小定理: 求模逆元的一个常用方法，当模数是质数时非常方便。
5. 预处理/空间换时间: 通过预先计算阶乘和逆阶乘，我们将每次计算组合数的时间从 $O(k)$ 或 $O(\log p)$ 降低到了 $O(1)$，这是处理多组查询的常用技巧。

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