题解 | 小红走矩阵

1. 路径分析

从 (1,1) 走到 (n,m)，小红总共需要走 n−1 步向下（D，Down）和 m−1 步向右（R，Right）。

因此，总的步数是 (n−1)+(m−1)=n+m−2 步。

每条不同的路径，都可以看作是一个包含 n−1 个 D 和 m−1 个 R 的序列。

2. 组合公式

问题转化为：在一个长度为 n+m−2 的序列中，选择 n−1 个位置放 'D' (向下走)，剩下的 m−1 个位置自然就是 'R' (向右走)。

总的走法数量就是从总步数 n+m−2 中选择向下走步数 n−1 的组合数，即：

C(n+m−2, n−1)​或C(n+m−2,m−1)​

3. 计算与取模

由于 n 和 m 的范围是 1≤n,m≤1000，总步数 N=n+m−2 最大可达 1998。我们需要计算 CNK​ 并对 M=998244353 取模，其中 K=n−1。

组合数 C(N,K)​=N!⋅(K!)^−1⋅((N−K)!)^−1 的计算步骤如下：

1. 计算分子：N!(modM)
2. 计算分母的逆元：(K!)^−1(modM) 和 ((N−K)!)^−1(modM)
3. 结果：C(N,K)​=N!⋅(K!)^−1⋅((N−K)!)^−1(modM)

由于 M=998244353 是一个质数，我们可以使用费马小定理来计算模逆元：a^(M−2)≡a^−1(modM)。

为了高效地计算，通常采用以下步骤：

1. 预处理阶乘： 事先计算出 0! 到 (n+m−2)! 对 998244353 取模的结果。
2. 快速幂： 编写一个快速幂函数 power(base, exp, mod) 来计算模逆元 aM−2(modM)。
3. 计算组合数：CNK​=fact[N]×power(fact[K],M−2,M)×power(fact[N−K],M−2,M)(modM)

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

using namespace std;

// 使用 long long 以确保中间计算不会溢出
using ll = long long;

// 定义模数 (一个大质数)
constexpr ll MOD = 998244353LL;

// 预处理阶乘的最大值。
// 对于 n x m (1000 x 1000) 的问题，最大需要的阶乘是 1998!
constexpr int MAXN = 2000;

// 存储预处理的阶乘值：fact[i] = i! % MOD
vector<ll> fact(MAXN + 1);

/**
 * @brief 快速幂函数：计算 (base^exp) % MOD
 * @param base 底数
 * @param exp 指数
 * @return (base^exp) % MOD 的结果
 */
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) { // 如果指数是奇数
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD; // 底数平方
        exp >>= 1; // 指数减半
    }
    return res;
}

/**
 * @brief 模逆元：使用费马小定理计算 (a)^(-1) % MOD
 * @details 根据费马小定理，a^(MOD-2) ≡ a^(-1) (mod MOD)，因为 MOD 是质数。
 * @param a 需要求逆元的数
 * @return a 的模逆元
 */
ll modInverse(ll a) {
    // 模数 MOD = 998244353 是质数
    return power(a, MOD - 2);
}

/**
 * @brief 预处理阶乘
 */
void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
}

/**
 * @brief 计算组合数 C(n, k) % MOD
 * @param n 总数
 * @param k 选择数
 * @return C(n, k) % MOD 的结果
 */
ll combinations(int n, int k) {
    // 边界条件：如果 k < 0 或 k > n，则组合数为 0
    if (k < 0 || k > n) {
        return 0;
    }

    // 核心公式: C(n, k) = n! * (k!)^(-1) * ((n-k)!)^(-1) % MOD
    // 其中 ^(-1) 表示模逆元

    ll numerator = fact[n]; // n! % MOD

    // (k!)^(-1) % MOD
    ll denominator1_inv = modInverse(fact[k]);

    // ((n-k)!)^(-1) % MOD
    ll denominator2_inv = modInverse(fact[n - k]);

    // 最终结果 = n! * (k!)^(-1) * ((n-k)!)^(-1) % MOD
    ll result = numerator;
    result = (result * denominator1_inv) % MOD;
    result = (result * denominator2_inv) % MOD;

    return result;
}


int main() {
    // 优化输入/输出操作
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1. 预处理阶乘
    precompute_factorials();

    int n, m;
    // 从标准输入读取矩阵的行数 n 和列数 m
    if (!(cin >> n >> m)) return 0;

    // 2. 计算总步数 N 和选择步数 K
    // 从 (1, 1) 到 (n, m)，需要 n-1 步向下，m-1 步向右
    int total_steps = (n - 1) + (m - 1); // N = n + m - 2
    int steps_to_choose = n - 1;         // K = n - 1 (或 m - 1)

    // 确保总步数不超过预处理范围
    if (total_steps > MAXN) {
        // 实际上对于 n, m <= 1000 不会发生，但最好有检查
        cerr << "Error: total steps exceeds MAXN limit." << endl;
        return 1;
    }

    // 3. 计算组合数 C(total_steps, steps_to_choose)
    ll result = combinations(total_steps, steps_to_choose);

    // 4. 输出结果
    cout << result << endl;

    return 0;
}