Gym103428G - Shinyruo and KFC

#题面

#题目描述

During your participation in this competition, Shinyruo is preparing to order KFC for the offline competition next week.

There are $n$ kinds of foods in KFC, and he plans to order $a_i$ number of the $i$-th food for every $i \in [1,n]$. Due to shortage of manpower, the total number of all kinds of foods is no larger than $10^5$.

After the competition, he will hand all the KFC out to $k$ teams. Each team can get different kinds of foods but for each kind it can get one at most. Now Shinyruo wants to know the number of ways to hand the desserts out. As he doesn’t know the number of participating teams, you need to calculate the answers for $k=1,2,\cdots,m$. As the answer can be large, print it modulo $998244353$.

#输入格式

The first line contains two integers $n, m$. ($1 \le m,n \le 5 \cdot 10^4$)

The second line contains $n$ integers $a_1, \cdots, a_n$. ($0\le a_i\le 10^5$, $\sum_{i=1}^n a_i\le 10^5$)

#输出格式

$m$ lines each contains one integer. The $i$-th integer indicates the answer of $k=i$ modulo $998244353$.

#输入输出样例

样例输入 #1

4 6
0 1 2 3

样例输出 #1

0
0
9
96
500
1800

#思路

一共有 $n$ 种食物，每种食物有 $a_i$ 个。食物个数总和不超过 $10^5$。

现在要把所有食物分给 $k$ 个人，每个人可以拿多种食物，但每种食物最多拿 $1$ 个。

对于人数 $k$ 从 $1$ 到 $m$，分别输出食物分配方案数。

答案对 $998244353$ 取模。

对于「一种食物共有 $a_i$ 个，全部分给 $k$ 个人，每人最多分一个」，就相当于「从 $k$ 人中选出 $a_i$ 人每人拿一个」，则第 $i$ 种食物的方案数为 $\displaystyle \binom{k}{a_i}$。

那么将 $n$ 种食物分给 $k$ 个人的总方案为 $\displaystyle \prod_{i = 1}^{n} \binom{k}{a_i}$。

然而这样做的时间复杂度为 $O(nm)$，会超时，因此需要进行一些优化。从数据范围中得知 $\sum_{i = 1}^n a_i \leq 10^5$，因此 $a_i$ 的种类数在 $\sqrt{10^5}$ 的级别，使用 unordered_map + 快速幂去重即可。

#代码

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
68
69
70
71
72
73
74
75

#include <iostream>
#include <unordered_map>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e4 + 5;
const int mod = 998244353;

int n, m, max, fac[N], inv[N], fac_inv[N];
std::unordered_map<int, int> map;

int binpow(int a, int b) {
    a %= mod;

    int res = 1;

    while (b) {
        if (b & 1) res = static_cast<long long>(res) * a % mod;
        a = static_cast<long long>(a) * a % mod;
        b >>= 1;
    }

    return res;
}

inline int C(int n, int m) {
    return static_cast<long long>(fac[n]) * fac_inv[m] % mod * fac_inv[n - m] % mod;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = static_cast<long long>(fac[i - 1]) * i % mod;
    }

    inv[0] = inv[1] = 1;
    for (int i = 2; i < N; i++) {
        inv[i] = static_cast<long long>(mod - mod / i) * inv[mod % i] % mod;
    }

    fac_inv[0] = fac_inv[1] = 1;
    for (int i = 2; i < N; i++) {
        fac_inv[i] = static_cast<long long>(fac_inv[i - 1]) * inv[i] % mod;
    }

    cin >> n >> m;

    for (int i = 1, x; i <= n; i++) {
        cin >> x;

        map[x]++;
        max = std::max(max, x);
    }

    for (int i = 1; i < max; i++) {
        cout << 0 << endl;
    }

    for (int k = max; k <= m; k++) {
        int res = 1;

        for (auto item : map) {
            res = static_cast<long long>(res) * binpow(C(k, item.first), item.second) % mod;
        }

        cout << res << endl;
    }

    return 0;
}