组合数学、容斥原理

真的太毒了，今天的模拟什么都没有做出来

这一题刚开始就到想了，最后也没有想出来

首先如果没有那个n的限制的话，就是简单的隔板法，组合数学。
但是有了n的限制就一下子麻烦了起来。
其实当时隐隐约约的感觉到了，只不过没有方向坚定地走下去。
我们在利用隔板法计算出来之后，在减去多余的。这是基本的想法。
问题就在于如何计算多余的？
这里利用了容斥的思想。
我们可以，先从k种抽出n个然后，在对k-n个隔板后，找一个放入n个
那么这就是至少有一个数超过n的可能
同样我们可以算出至少又两个数超过n的可能
。。。。。
因为是相互包含的关系，所以容斥原理。

但是我给出了疑惑，其实我认为之前所算出来的并不是至少i个超过n的可能。
因为如果是的话，直接减去第一个不就行了嘛。

这里面还是有重复的，容斥就是去消去这个重复的。

然后我写了代码，刚开始是这样的：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int max_n = 2e5+100;
ll n,m,k;
ll POW(ll base,ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1)
            ans = ((ans % mod) * (base % mod)) % mod;
        p >>= 1;
        base = ((base % mod) * (base % mod)) % mod;
    }return ans;
}
ll inv(ll a){
    return POW(a,mod-2);
}
ll j[max_n];
ll C(ll a,ll b){
    if (a<b)return 0;
    return j[a]*inv((j[a-b]*j[b]%mod))%mod;
}
ll he[2] = {1,-1};
int main(){
    j[0]=1;
    for (ll i=1;i<max_n;++i)j[i]=i*j[i-1]%mod;
    int t;scanf("%d",&t);
    while (t--){
        scanf("%lld %lld %lld",&n,&m,&k);
        ll ans = C(k+m-1,m-1);
        for (ll i=1;i<=m&&i*n<=k;++i){
            ans = (ans + he[i&1]*(C(m,i)*C(k+m-i*n-1,m-1)%mod)+mod)%mod;
        }printf("%lld\n",ans);
    }
}

t了！！我是真的艹了
学到了一手，关于阶乘逆元的高效求法：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int max_n = 2e5+100;
ll n,m,k;
ll POW(ll base,ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1)
            ans = ((ans % mod) * (base % mod)) % mod;
        p >>= 1;
        base = ((base % mod) * (base % mod)) % mod;
    }return ans;
}
ll inv(ll a){
    return POW(a,mod-2);
}
ll j[max_n],finv[max_n];
ll C(ll a,ll b){
    if (a<b)return 0;
    return j[a]*finv[a-b]%mod*finv[b]%mod;
}
ll he[2] = {1,-1};
int main(){
    j[0]=1;finv[0]=1;
    for (ll i=1;i<max_n;++i){
        j[i]=i*j[i-1]%mod;
        finv[i] = finv[i-1]*inv(i)%mod;
    }
    int t;scanf("%d",&t);
    while (t--){
        scanf("%lld %lld %lld",&n,&m,&k);
        ll ans = C(k+m-1,m-1);
        for (ll i=1;i<=m&&i*n<=k;++i)
            ans = (ans + he[i&1]*(C(m,i)*C(k+m-i*n-1,m-1)%mod)+mod)%mod;
        printf("%lld\n",ans);
    }
}