AtCoder Beginner Contest 248C Dice Sum

题目链接

题意

给定三个整数$N,M,K$，求有多少种满足以下条件的序列$A$：

1. $A$长度为$N$；
2. $1\le A_i\le M(1\le i\le N)$
3. ${\sum }_{i=1}^N{A}_i\le K$

最后的结果对998244353取模。

思路

对于每一个$A_i$，可以用$f(x)=0+x+x^2+...+x^M=x\frac{1-x^M}{1-x}$来表示。

令$F(x)=f(x{)}^N$，那么结果就是${\sum }_{i=0}^k[x^i]F(x)$。

令$G(x)=F(x)\ast (1+x+x^2+...)=F(x)\ast \frac{1}{1-x}$，则
$$\begin{array}{ccc}[x^k]G(x)& =& {\sum }_{i=0}^k[x^k]F(x)\ast [x^{k-i}]\frac{1}{1-x}\\ & & \\ & =& {\sum }_{i=0}^k[x^k]F(x)\end{array}$$

又因：
$$G(x)=F(x)\ast \frac{1}{1-x}=x^N(1-x^M{)}^N(1-x{)}^{-(N+1)}$$

故：$[x^k]G(x)=[x^{k-N}](1-x^M{)}^N(1-x{)}^{-(N+1)}$。

其中
$$(1-x^M{)}^N=\sum _{i=0}^N(\genfrac{}{}{0ex}{}{N}{i})(-x^M{)}^i=\sum _{i=0}^N(-1{)}^i\frac{N!}{i!(N-i)!}{x}^{i\times M}$$

令$h(x)=(1-x{)}^{-(N+1)}$，则：
$$\begin{array}{ccccc}h(x)& =& (1-x{)}^{-N-1}& & \\ & & & & \\ h^{\prime }(x)& =& (-N-1)(-1)(1-x{)}^{-N-2}& =& (N+1)(1-x{)}^{-N-2}\\ & & & & \\ h^{\prime \prime }(x)& =& (-N-1)(-N-2)(-1{)}^2(1-x{)}^{-N-3}& =& (N+1)(N+2)(1-x{)}^{-N-3}\\ & & & & \\ \cdots & & & & \\ & & & & \\ h^{(i)}(x)& =& (N+1)(N+2)\cdots (N+i)(1-x{)}^{-N-3}& =& \frac{(N+i)!}{N!}(1-x{)}^{-N-3}\\ & & & & \end{array}$$

由泰勒公式，得：
$$h(x)=h(0)+\frac{h^{\prime }(0)x}{1!}+\frac{h^{\prime \prime }(0)x^2}{2!}+...+\frac{h^{(n)}(0)x^n}{n!}+...$$

$$[x^i]h(x)=\frac{h^{(i)}(0)}{i!}{x}^i=\frac{(N+i)!}{N!i!}{x}^i$$

结果为：
$$\begin{array}{ccc}[x^{k-N}](1-x^M{)}^N(1-x{)}^{-(N+1)}& =& {\sum }_{i\ge 0}(-1{)}^i\frac{N!}{i!(N-i)!}\times \frac{(N+(K-N-i\times M))!}{N!(K-N-i\times M)!}\\ & & \\ & =& {\sum }_{i\ge 0}(-1{)}^i\frac{N!}{i!(N-i)!}\times \frac{(N+(K-N-i\times M))!}{N!(K-N-i\times M)!}\\ & & \\ & =& {\sum }_{i\ge 0}(-1{)}^i\frac{(K-i\times M)!}{(K-N-i\times M)!\times i!(N-i)!}\\ & & \end{array}$$

其中$i\times M\le K-N$。

AC的代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
const int N = 1e6 + 10;

ll fac[N], n, m, k;
ll power(ll a, ll b) {
    
    ll res = 1;
    while (b) {
    
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll x) {
     return power(x, mod - 2); }

void init() {
    
    fac[0] = 1;
    for (int i = 1; i <= N - 10; i++) fac[i] = fac[i - 1] * i % mod;
}

int main() {
    
    init();
    cin >> n >> m >> k;
    ll res = 0;
    for (int i = 0;; i++) {
    
        if (i * m > k - n) break;
        ll tmp = fac[k - i * m] * inv(fac[i]) % mod * inv(fac[n - i]) % mod *
                 inv(fac[k - n - i * m]) % mod;

        res = ((res + (i % 2 ? -1 : 1) * tmp) % mod + mod) % mod;
    }
    cout << res;

    return 0;
}