题解 | 小红走矩阵

#include<bits/stdc++.h>
using namespace std;
//根据排列组合的小知识，从起点到终点一共要走n-1步向下，m-1步向右
//因此总步数为(m+n-2)!/(m-1!*n-1!),其中(m+n-2)!为所有元素全排列，除去相同元素内部排列即可
//由于这个数计算量太大，因此需要使用费马小定理与逆元的知识
const int MOD=998244353;
long long fact[2000];//存储阶乘，m、n均小于1000

//快速幂
long long qpow(long long base,long long power){
    long long result = 1;
    base = base % MOD;//先取模防止溢出
    while(power>0){
        if(power % 2 == 1){//指数为奇数
            result = result * base % MOD;
        }
        base = base*base %MOD;
        power = power >> 1;//除2
    }
    return result;
}

//预处理
void pre_fact(){
    fact[0]=1;
    for(int i=1;i<2000;i++){
        fact[i] = fact[i-1] * i % MOD;
    }
}

//计算组合数对MOD取模
long long C(int a,int b){
    return fact[a] * qpow(fact[b],MOD-2) % MOD * qpow(fact[a-b],MOD-2) % MOD;//逆元小技巧
}

int main(){
    int m,n;
    cin>>m>>n;
    pre_fact();
    long long ans = C(m+n-2,n-1);
    cout<<ans<<endl;
    return 0;
}
//ciallo~