Submission #70655742

---

Source Code Expand

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

const long long MOD = 998244353;

struct Comb {
    int nmax;
    vector<long long> fact, ifact;
    long long modpow(long long a, long long e){
        long long r=1%MOD;
        while(e){
            if(e&1) r=r*a%MOD;
            a=a*a%MOD;
            e>>=1;
        }
        return r;
    }
    Comb(int n): nmax(n), fact(n+1), ifact(n+1){
        fact[0]=1;
        for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%MOD;
        ifact[n]=modpow(fact[n], MOD-2);
        for(int i=n;i>0;i--) ifact[i-1]=ifact[i]*i%MOD;
    }
    long long C(int n,int k){
        if(n<0||k<0||k>n) return 0;
        return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, S;
    if(!(cin >> N >> M >> S)) return 0;
    if(1LL*N*M < S){ cout << 0 << '\n'; return 0; }
    Comb cb(N + S);
    long long ans = 0;
    int step = M + 1;
    for(int k=0; 1LL*k*step<=S && k<=N; ++k){
        long long ways_upper = cb.C(N, k);
        long long ways_sum = cb.C(S - k*step + N - 1, N - 1);
        long long term = ways_upper * ways_sum % MOD;
        if(k&1) ans = (ans - term + MOD) % MOD;
        else ans = (ans + term) % MOD;
    }
    cout << ans % MOD << '\n';
    return 0;
}

Submission Info

Judge Result