Submission #68259679

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
template<typename T, typename T2>
inline void chmin(T &x, T2 &&y) { x = min(x, y); }
template<typename T, typename T2>
inline void chmax(T &x, T2 &&y) { x = max(x, y); }
typedef long long ll;

const int N = 4e5 + 5, p = 998244353;

int fac[N], ifac[N];

ll qpow(ll a, ll b)
{
    if(!b) return 1;
    return ((b & 1) ? a : 1ll) * qpow(a * a % p, b >> 1) % p;
}

void init()
{
    fac[0] = ifac[0] = 1;
    for(int i = 1; i < N; i ++) fac[i] = 1ll * fac[i - 1] * i % p;
    ifac[N - 1] = qpow(fac[N - 1], p - 2) % p;
    for(int i = N - 2; i >= 1; i --) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % p;
}

ll C(ll a, ll b)
{
    if(a < b || a < 0 || b < 0) return 0;
    return 1ll * fac[a] * ifac[b] % p * ifac[a - b] % p;
}

ll S(ll al, ll ar, ll b)
{
    return (C(ar + 1, b + 1) - C(al, b + 1) + p) % p;
}

void solve()
{
    int n, m, k; cin >> n >> m >> k;
    if(k < n + m - 2) return cout << 0 << "\n", void();   
    if(k == n + m - 2) return cout << C(n + m - 2, n - 1) << "\n", void();
    int s = (1ll * n * (m - 1) + 1ll * m * (n - 1) - (n + m - 2)) % p;
    if(k == n + m - 1) return cout << C(n + m - 2, n - 1) * s % p << "\n", void();
    int ans = C(n + m - 2, n - 1) * (1ll * s * (s - 1) / 2 % p) % p;
    // cerr << ans << endl;
    ans = (ans - C(n + m - 4, n - 2) * (n + m - 3)) % p;
    // cerr << ans << endl;
    // rep(i, 1, n - 1) ans = (ans + C(m + n - 2 - i, m) * (m - 1)) % p;
    // rep(i, 1, m - 1) ans = (ans + C(m + n - 2 - i, n) * (n - 1)) % p;
    ans = (ans + S(m + n - 2 - (n - 1), m + n - 2 - 1, m) * (m - 1)) % p;
    ans = (ans + S(m + n - 2 - (m - 1), m + n - 2 - 1, n) * (n - 1)) % p;
    cout << (ans + p) % p << "\n";
}

signed main()
{
    init();
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin >> t;while(t --) solve();

    return 0;
}

Submission Info

Judge Result