Submission #68250531

---

Source Code Expand

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int N = 2e5 + 10;
const int MOD = 998244353;

ll qpow(ll a, ll b, int p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

template<typename T>
struct Binom
{
    vector<T> fact;   // fact[i]存储i的阶乘
    vector<T> infact; // infact[i]存储i的阶乘的逆元

    explicit Binom(int n){
        init(n);
    }

    void init(int n){
        fact.resize(n + 1);
        infact.resize(n + 1);

        fact[0] = infact[0] = 1;
        for (int i = 1; i <= n; i++){
            fact[i] = fact[i - 1] * i % MOD;
        }

        infact[n] = qpow(fact[n], MOD - 2, MOD);

        for (int i = n; i >= 1; i--){
            infact[i - 1] = infact[i] * i % MOD;
        }
    }

    T C(int a, int b){
        if (a < 0 || b < 0 || a < b)  return 0;
        return fact[a] * infact[a - b] % MOD * infact[b] % MOD;
    }

    T Catalan(int n){
        return C(2 * n, n) * qpow(n + 1, MOD - 2, MOD) % MOD;
    }
};

int n, m, k;
Binom<ll> binom(6e5);
int inv2;

void solve()
{
    cin >> n >> m >> k;
    ll ans = 0;
    if(k < n + m - 2){
        ans = 0;
    }
    else if(k == n + m - 2){
        ans = binom.C(n + m - 2, n - 1);
    }
    else if(k == n + m - 1){
        ans = binom.C(n + m - 2, n - 1) * ((1ll * n * (m - 1) % MOD + 1ll * m * (n - 1) % MOD - (n + m - 2) + MOD) % MOD) % MOD;
    }
    else if(k == n + m){
        // 最短路长度为n+m-2
        ans += binom.C(n + m - 2, n - 1) * ((1ll * n * (m - 1) % MOD + 1ll * m * (n - 1) % MOD - (n + m - 2) + MOD) % MOD) % MOD 
                * ((1ll * n * (m - 1) % MOD + 1ll * m * (n - 1) % MOD - (n + m - 2) + MOD) % MOD - 1 + MOD) % MOD * inv2 % MOD;
        ans %= MOD;
        ans -= binom.C(n + m - 4, n - 2) * (n + m - 3) % MOD;
        ans = (ans + MOD) % MOD;

        // 最短路长度为n+m
        ans += binom.C(n + 1 + m - 3, n + 1) * (n - 1) % MOD;
        ans %= MOD;
        ans += binom.C(n - 3 + m + 1, m + 1) * (m - 1) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}


signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    inv2 = qpow(2, MOD - 2, MOD);
    int T=1; cin>>T; while(T--)
    solve();
    return 0;
}

Submission Info

Judge Result