题解 | 小红走矩阵

思路：

用二维vector统计重复路径(走过的置1）用dfs()递归走右下 用stay()检视路径是否合法，很明显 这会超时

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cnt,n,m;//cnt为路径数目
vector<vector<ll>> cc(1e3+1,vector<ll>(1e3+1));//记录重复路径

bool stay(ll x,ll y){//路径是否合法
    if(x>n||y>m||x<1||y<1) return false;
    if(cc[x][y]==1) return false;
    return true;
}

void dfs(ll x,ll y){//走向右下
    if(x==n && y==m){//到达终点
        cnt=(++cnt)%998244353;
        return;
    }
    if(stay(x+1,y)){
        cc[x][y]=1;
        dfs(x+1,y);
        cc[x][y]=0;   
    }
    if(stay(x,y+1)){
        cc[x][y]=1;
        dfs(x,y+1);
        cc[x][y]=0;   
    }    
    return;
}
int main() {
    cin>>n>>m;
    dfs(1,1);//开始
    cout<<cnt;
}

这题可以用组合数解决：

假设要从 (1,1) 走到 (2,3)（n=2，m=3）：要到终点，必须走：1次向下（↓） + 2次向右（→），总步数是 1+2=3；

问题转化为：在 3 步中，选 1 步走「向下」（剩下的自然走「向右」），有多少种选法？C(3,1)=3（或选 2 步走向右，C(3,2)=3，结果一样）。

再加上快速幂就可以得到

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;
ll cnt,n,m;
//vector<vector<ll>> cc(1e3+1,vector<ll>(1e3+1));

// 快速幂
ll qpow(ll a, ll b) {
    ll c = 1;
    while (b) {
        if (b & 1) c = c * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return c;
}

// 预处理阶乘和逆元阶乘
ll aa[2005], bb[2005];
void init() {
    aa[0] = 1;
    // 预处理阶乘
    for (int i = 1; i <= 2000; i++) aa[i] = aa[i-1] * i % MOD;
    bb[2000] = qpow(aa[2000], MOD-2);
    for (int i = 1999; i >= 0; i--) bb[i] = bb[i+1] * (i+1) % MOD;
}

// 计算组合数 C(a, b) mod MOD
ll C(ll a, ll b) {
    if (a < 0 || b < 0 || a < b) return 0;
    return aa[a] * bb[b] % MOD * bb[a - b] % MOD;
}

int main() {
    init(); //初始化
    cin>>n>>m;
    cnt = C(n + m - 2, n - 1) % MOD;
    cout<<cnt;
}

改用C来实现就是

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long ll;

const ll MOD = 998244353;
ll cnt, n, m,aa[2005], bb[2005];

// 快速幂
ll qpow(ll a, ll b) {
    ll c = 1;
    while (b) {
        if (b & 1) c = c * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return c;
}


// 预处理阶乘和逆元阶乘（算组合数）
void init() {
    aa[0] = 1;
    // 预处理阶乘
    for (int i = 1; i <= 2000; i++) {
        aa[i] = aa[i-1] * i % MOD;
    }
    // 预处理逆元阶乘
    bb[2000] = qpow(aa[2000], MOD - 2);
    for (int i = 1999; i >= 0; i--) {
        bb[i] = bb[i+1] * (i+1) % MOD;
    }
}

// 计算组合数 C(a, b) mod MOD
ll C(ll a, ll b) {
    if (a < 0 || b < 0 || a < b) return 0;
    ll res = aa[a] * bb[b] % MOD;
    res = res * bb[a - b] % MOD;
    return res;
}

int main() {
    init(); 
    scanf("%lld%lld", &n, &m);
    // 计算组合数 C(n+m-2, n-1)
    cnt = C(n + m - 2, n - 1) % MOD;
    printf("%lld\n", cnt);
    
    return 0;
}