In computer science, a character is a letter, a digit, a punctuation mark or some other similar symbol. Since computers can only process numbers, number codes are used to represent characters, which is known as character encoding. A character encoding system establishes a bijection between the elements of an alphabet of a certain size n and integers from 0 to n−1. Some well known character encoding systems include American Standard Code for Information Interchange (ASCII), which has an alphabet size 128, and the extended ASCII, which has an alphabet size 256.

For example, in ASCII encoding system, the word 𝚠𝚍𝚢 is encoded as [119, 100, 121], while 𝚓𝚜𝚠 is encoded as [106, 115, 119]. It can be noticed that both 119+100+121=340 and 106+115+119=340, thus the sum of the encoded numbers of the two words are equal. In fact, there are in all 903 such words of length 3 in an encoding system of alphabet size 128 (in this example, ASCII). The problem is as follows: given an encoding system of alphabet size n where each character is encoded as a number between 0 and n−1 inclusive, how many different words of length m are there, such that the sum of the encoded numbers of all characters is equal to k?

Since the answer may be large, you only need to output it modulo 998244353.

大致题意 📖

给定n,m,kn,m,k

x1+x2+x3++xm=k0<=xi<nx_1 + x_2 + x_3 + \cdots + x_m = k (0 <= x_i < n)

求该不定方程式解的数量

链接 🔗

「CodeForces 1198C」 Matching vs Independent Set

题解 ❓

在不考虑 xi<nx_i<n可以用隔板法得到满足的数量为 Cm+x1m1C^{m-1}_{m+x-1}
当然,如果存在xi>=nx_i >= n,我们应当去掉这些情况
如果存在一个xi>=nx_i >= n,则该情况的总数为 Cm1)C^1_{m}) ,此时相当于我们已经选了一个nn,剩下的容量为m+kn1m+k-n-1,然后继续插板法,可以得到数量Cm+k1m1Cm1Cm+kn1m1C_{m+k-1} ^{m-1} - C_m^1 * C_{m+k-n-1}^{m-1},但是这样我们多减去了出现2个$x_i >=n $的情况,于是我们通过容斥原理解决

ans=Cm+x1m1+i=1mCm1Cm+kn1m1(1)ians = C^{m-1}_{m+x-1} + \sum_{i=1}^m C_m^1 * C_{m+k-n-1}^{m-1} * (-1)^i

代码

const ll N = 2e5+10;
const ll mod = 998244353;
struct
{
    ll fac[N],inv[N],Finv[N];//分别代表逆元,阶乘,阶乘逆元;
    void init()
    {
        fac[0] = 1ll, Finv[0]=1ll,inv[1]=1ll;
        for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        for(int i=1;i<N;i++)
        {
            fac[i]=fac[i-1]*i%mod;
            Finv[i]=Finv[i-1]*inv[i]%mod;
        }
    }
    ll C(ll n,ll m)
    {
        if(n<0||m<0||m>n) return 0;
        return fac[n] * Finv[m] %mod * Finv[n-m] %mod;
    }
}comb;
int main()
{
//    __IN;__OUT
    ll T;RLL(T);
    comb.init();
    while(T--)
    {
        ll n,m,k;RLL3(n,m,k);
        ll res = 0;
        for(int i=0;i*n<=k;i++)
        {
            if(i&1) res=(res-comb.C(m,i)*comb.C(k-i*n+m-1,m-1) % mod + mod)%mod;
            else res=(res+comb.C(m,i)*comb.C(k-i*n+m-1,m-1)%mod)%mod;
        }
        PLN(res);
    }
    return 0;
}