Skip to content

Gym103428G - Shinyruo and KFC

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

After the competition, he will hand all the KFC out to kk 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, ,mk=1,2,\cdots,m. As the answer can be large, print it modulo 998244353998244353.

#输入格式

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

The second line contains nn integers a1, ,ana_1, \cdots, a_n. (0ai1050\le a_i\le 10^5, i=1nai105\sum_{i=1}^n a_i\le 10^5)

#输出格式

mm lines each contains one integer. The ii-th integer indicates the answer of k=ik=i modulo 998244353998244353.

#输入输出样例

样例输入 #1

4 6
0 1 2 3

样例输出 #1

0
0
9
96
500
1800

#思路

一共有 nn 种食物,每种食物有 aia_i 个。食物个数总和不超过 10510^5

现在要把所有食物分给 kk 个人,每个人可以拿多种食物,但每种食物最多拿 11 个。

对于人数 kk11mm,分别输出食物分配方案数。

答案对 998244353998244353 取模。

对于「一种食物共有 aia_i 个,全部分给 kk 个人,每人最多分一个」,就相当于「从 kk 人中选出 aia_i 人每人拿一个」,则第 ii 种食物的方案数为 (kai)\displaystyle \binom{k}{a_i}

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

然而这样做的时间复杂度为 O(nm)O(nm),会超时,因此需要进行一些优化。从数据范围中得知 i=1nai105\sum_{i = 1}^n a_i \leq 10^5,因此 aia_i 的种类数在 105\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;
}