DDOSvoid's Blog

2021牛客多校4 G Product

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11255/G

简要题意：给定 $n,k,D$，对于一个长度为 $n$ 的序列 $a_i$，我们定义它的价值为 $\frac{D!}{\prod_{i=1}^n(a_i+k)!}$，求对于所有满足 $\sum_{i=1}^n a_i=D,a_i\ge 0$ 的序列 $a_i$ 的价值和

$n,k\le 50,D\le 10^8$

Solution

我们考虑转换一下原式，得到 $\frac{(D+nk)!}{\prod_{i=1}^n(a_i+k)!}\times \frac{D!}{(D+nk)!}$​，其中 $\sum_{i=1}^n a_i=D,0\le a_i\le D$

容易得到这个式子的前半部分等价于 $EGF$，$x^{D+nk}^n$

它的组合意义很明显，有 $n$ 种物品，每种物品有 $D+k$ 个，且至少选 $k$ 个，一共选 $D+nk$ 个物品做排列的方案数

然后对于这个东西，我们直接暴力二项式展开算系数即可

时间复杂度 $O(D+n^2k)$

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <unordered_map>
#define maxn 110
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}       

int n, k, D;

ll C[maxn][maxn], fac[maxn], inv[maxn];
void init_C(int n, int k) {
    fac[0] = 1; for (int i = 1; i <= k; ++i) fac[i] = fac[i - 1] * i % p;
    inv[k] = pow_mod(fac[k], p - 2); for (int i = k - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
    
    for (int i = 0; i <= n; ++i) C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
}

unordered_map<int, ll> mp; ll facD;
void init() {
    int fac = 1;
    for (int i = 1; i <= D; ++i) fac = 1ll * fac * i % p;
    facD = fac;
    for (int i = D; i <= D + n * k; ++i) {
        mp[i] = pow_mod(fac, p - 2); 
        fac = 1ll * fac * (i + 1) % p; 
    }
}

ll A[10000], B[10000], tmp[10000]; int n1, n2;
void Mul(ll *A, ll *B) {
    int n = n1 + n2;
    for (int k = 0; k <= n; ++k) {
        tmp[k] = 0;
        for (int i = 0; i <= min(n1, k); ++i)
            if (k - i <= n2) tmp[k] = (tmp[k] + A[i] * B[k - i]) % p;
    }
    for (int i = 0; i <= n; ++i) A[i] = tmp[i]; n1 = n;
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n >> k >> D; init_C(n, k); init(); 
    if (k == 0) return cout << pow_mod(n, D) << "\n", 0;
    for (int i = 0; i < k; ++i) B[i] = inv[i]; n2 = k - 1;
    A[0] = 1; n1 = 0; ll ans = 0; 
    for (int i = 0, type = 1; i <= n; ++i, type = -type) {
        ll sum = 0;
        for (int j = 0; j <= n1; ++j)
            sum = (sum + A[j] * pow_mod(n - i, D + n * k - j) % p * mp[D + n * k - j]) % p;
        ans = (ans + type * C[n][i] * sum) % p; Mul(A, B);
    } ans = ans * facD % p;
    cout << (ans + p) % p << "\n";
    return 0; 
}