hdu6397

组合+容斥

/*
HDU 6397 A: Character Encoding 组合计数+容斥
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6397
题意:n m k  选择区间[0,n-1]的数字，每个数字可以选择最多不超过m个使得他们的和等于k；
组合计数+容斥原理 经典的球盒问题
由于和为k,不妨先进行设置每一份的大小为多少，然后对剩下的部分直接进行计算，那么再不存在
n的限制时，答案即为C(k+m-1,m-1);
由于存在限制条件，只能选0~n-1的数
如果只有c个，那么这个数x’>=n一定成立。现在我们做这样一个操作，将所有大于等于n的x全部减去n，这样问题由原来的x 1 + x 2 + . . . x m = k x_1+x_2+...x_m=kx 
1
​    
 +x 
2
​    
 +...x 
m
​    
 =k转换成了x1+x2+x3+.....+xm
 =k−n∗c原来的x1…xm可能是大于等于n的，但是转化以后的x’全部是小于n的而且大于0，这个就相当于转换成了上述没有限制的一个子问题。就可以用上面说的方法求数量     
*/
#include<bits/stdc++.h>
using namespace std;

#define e exp(1)
#define pi acos(-1)
#define mod 998244353
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a))
int gcd(int a,int b){return b?gcd(b,a%b):a;}

const int maxn=2e5+5;
ll n,m,k;
ll f[maxn],inv[maxn];
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
void init()
{
    f[0]=inv[0]=1;
    for(int i=1; i<maxn; i++)
    {
        f[i]=f[i-1]*i%mod;
        inv[i]=qpow(f[i],mod-2);
    }
}

ll C(ll n,ll m)
{
    return f[n]*inv[n-m]%mod*inv[m]%mod;
}
int main()
{
    init();
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        ll ans=C(k+m-1,m-1);
        ll len=min(k/n,m);
        for(int i=1; i<=len; i++)
        {
            if(i&1)ans=(ans-C(m,i)*C(k+m-1-i*n,m-1)%mod+mod)%mod;
            else ans=(ans+C(m,i)*C(k+m-1-i*n,m-1)%mod)%mod;
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}