HDOJ6397

发表于 | 分类于

题目在此HDOJ6397

题意

抽象出来：
求满足$\sum_{i=1}^m{a_i}=k$且$a_i\in[0,n-1] \cap N$的方案个数 (1,1,2)和(1,2,1)算一种方案 以此类推

分析

这题是2018多校第一题 明显题解讲的东西不是现场能想出来的 回忆下整数分拆问题 和这题有点类似 可以采用隔板法或生成函数的做法 那我们这里来推一下生成函数的做法

公式推理

通过生成函数的计算方式我们知道 多项式 $(1+x+x^2+\cdots+x^{n-1})^m$的$x^k$项的系数就是答案
然后我们化简一下这个多项式
$$ \begin{align*} & (1+x+x^2+\cdots+x^{n-1})^m \\ & =(\frac{1-x^n}{1-x})^m \\ & =(1-x^n)^m\cdot (1-x)^{-m} \\ \end{align*} $$
好了到了这一步 得把它给展开
第一项就是正常的二项式展开 由于第二项的次数是负的 要泰勒展开（这里用的是泰勒展开 用广义牛顿二项式展开也能得到相同的结论） 那么上式即
$\sum_{i=0}^m{C_m^i}(-x^n)^i\cdot \sum_{i=0}^\infty{C_{m+i-1}^{i-1}x^i}$
要求$x^k$的系数 注意到第二项和函数是无穷级数 那么枚举第一项和函数中的项 答案是
$\sum_{i=0}^m{(-1)^iC_m^ix^{ni}\cdot C_{m+k-ni-1}^{ni-1}x^{k-ni}}$
即
$\sum_{i=0}^m{(-1)^iC_m^i\cdot C_{m+k-ni-1}^{ni-1}x^{k}}$
要注意 $k-ni\ge 0$ 即 $i\le \frac{k}{n}$
所以得把求和上限改了
那么答案就是 $\sum_{i=0}^{\frac{k}{n}}{(-1)^iC_m^i\cdot C_{m+k-ni-1}^{ni-1}}$

复杂度

求和复杂度是$O(\frac{k}{n})$ 内部的组合数暴力转移复杂度是 $O(n)$ 所以一次询问的复杂度是$O(k)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>

typedef long long ll;
const int N = 1e5 + 10;
const ll MOD = 998244353;

using namespace std;

ll inv[N<<1];

//这是线性处理逆元
inline void init(){
    inv[1] = 1;
    for (int i = 2; i < (N<<1); i++)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}

int main() {
    int t;
    cin >> t;
    init();
    while (t--) {
        ll n, m, k;
        cin >> n >> m >> k;
        ll ans = 0;
        ll sig = 1;
        ll cur1 = 1, cur2 = 1;
        for (int i = 0; i < m - 1; i++) {
            cur2 = cur2*(m + k - i - 1) % MOD*inv[i + 1] % MOD;
        }
        for (int i = 0; i <= k / n; i++) {
            ans += cur1*cur2%MOD*sig%MOD;
            ans = (ans%MOD + MOD) % MOD;
            sig = (sig == 1 ? -1 : 1);
            if (i + 1 <= k / n) {
                cur1 = cur1*(m - i) % MOD*inv[i + 1] % MOD;
                for (int j = m + k - n*i - 1; j > m + k - n*(i + 1) - 1; j--) {
                    cur2 = cur2*(j - m + 1) % MOD*inv[j] % MOD;
                }
            }
        }
        cout << ans%MOD << endl;
    }
    return 0;
}