Submission #70662393

---

Source Code Expand

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

const int MOD = 998244353;

long long modpow(long long a, long long e){
    long long r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD; e>>=1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M,S; 
    if(!(cin>>N>>M>>S)) return 0;

    int LIM = N + S + 5;
    vector<long long> fact(LIM), invfact(LIM);
    fact[0]=1;
    for(int i=1;i<LIM;i++) fact[i]=fact[i-1]*i%MOD;
    invfact[LIM-1]=modpow(fact[LIM-1], MOD-2);
    for(int i=LIM-2;i>=0;i--) invfact[i]=invfact[i+1]*(i+1)%MOD;

    auto C = [&](int n,int r)->long long{
        if(r<0||r>n||n<0) return 0;
        return fact[n]*invfact[r]%MOD*invfact[n-r]%MOD;
    };

    long long ans=0;
    int tmax = S/(M+1);
    for(int j=0;j<=tmax;j++){
        long long ways = C(N, j) * C(S - j*(M+1) + N - 1, N - 1) % MOD;
        if(j&1) ans = (ans - ways + MOD) % MOD;
        else ans = (ans + ways) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result