排列组合---隔板法
1、定义
隔板法就是在n个元素间插入（b-1）个板，即把n个元素分成b组的方法。C(n-1,b-1)
2、条件
隔板法必须满足三个条件：
（1）这n个元素必须相同,（2）所分成的每一组至少分得一个元素，（3）分成的组别彼此差异。
3、示例
（1）例如：某校组建一球队需16人，该校共10个班级，且每个班至少分配一个名额，共有几种情况。C（16-1,10-1）。
对n件相同物品（或名额）分给m个人（或位置），允许若干个人（或位置）为空的问题,可以看成将这n件物品分成m组，允许若干组为空的问题.将n件物品分成m组，需要m-1块隔板，将这n件物品和m-1块隔板排成一排，占n+m-1位置，从这n+m-1个位置中选m-1个位置放隔板，因隔板无差别，故隔板之间无序，是组合问题，故隔板有Cn+m-1 m-1种不同的方法，再将物品放入其余位置，因物品相同无差别，故物品之间无顺序，是组合问题，只有1种放法，根据分步计数原理，共有Cn+m-1 m-1×1=Cn+m-1 m-1种排法
（2）求方程x1+x2+…+xk=n的非负整数解或正整数解
解：正整数解：转化为10个相同的小球装入4个不同的盒子，每盒至少有一个，有C(10-1,4-1)=84种。
非负整数解：转化为10个相同的小球装入4个不同的盒子，可以有空盒，有C(10+4-1,4-1)种。
（3）X个相同的球放入Y个不相同的盒子中,要求每个盒子至多N个球至少0个球,共有多少种不同的放法？
首先对于m个球放入Y个盒中,每个盒中至少一个球的放法用隔板法可以得到，即相当于在m-1个位置中放入Y-1个挡板将m个球分为Y份，这样每份至少为1，为 ,
而X个球放入Y个盒中,每个盒中至少0个球的放法相当于X+Y个球放入Y个盒中,每个盒中至少一个球的放法，即相当于将X+Y个球分入Y个盒中，再从每个盒中取出1球，为
而对于指定t个盒子（例如1,2，3，···，t号盒子）中的球数至少为N+1个球的放法等同于将（X-t*（N+1））个球放入Y个盒中,每个盒中至少0个球的放法，即（X-t*（N+1））个球放入Y个盒中后，再在指定的t个盒中各放入N+1个球，为
根据容斥原理，每个盒子至多N球的放法为 总放法-所有指定一个盒子的球数大于N的方法+所有指定两个盒子的球数大于N的方法-所有指定三个盒子的球数大于N的方法+······
即为
其中
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n,m,k;
const ll M=2*1e5+5;
ll fact[M],ifact[M];//fact[i]是i的阶乘，ifact[i]是阶乘的除法逆元，两者用于求组合数
ll pow_mod(ll n,ll k,ll mod) //快速幂求n^k余m的结果
{
ll res=1;
n=n%mod;
while(k>0)
{
if(k&1)
res=res*n%mod;
n=n*n%mod;
k>>=1;
}
return res;
}
void init()//初始化
{
fact[0]=ifact[0]=1;
for(int i=1;i<M;++i)
{
fact[i]=(fact[i-1]*i)%mod;
ifact[i]=pow_mod(fact[i],mod-2,mod);
}
}
ll C(ll n,ll m)//求组合数
{
if(n<m)
return 0;
return fact[n]*ifact[m]%mod*ifact[n-m]%mod;
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&m,&k);
ll X=k,Y=m,N=n-1;
ll ans=C(X+Y-1,Y-1);
for(ll t=1;t<=X/(N+1);t++)
{
if((t&1)==0)
{
ans=(ans+C(Y,t)*C(X+Y-1-t*(N+1),Y-1)%mod)%mod;
}
else
{
ans=(ans-C(Y,t)*C(X+Y-1-t*(N+1),Y-1)%mod+mod)%mod;
}
}
printf("%I64d\n",ans%mod);
}
return 0;
}