CCPC2021-威海站 — G. Desserts

题目链接

题面

During your participation in CCPC-Weihai, Yukino is preparing desserts for every team of this competition.

There are n kinds of desserts in total, and she has prepared a_i number of the ii-th dessert for every i∈[1,n]. Due to shortage of manpower, the total number of all kinds of desserts is no larger than 10⁵.

After the competition, she will hand all the desserts out to k teams. Each team can get different kinds of desserts but for each kind it can get one at most.

Now Yukino wants to know the number of ways to hand the desserts out. As she doesn’t know the number of participating teams, you need to calculate the answers for k=1,2,⋯,m.

As the answer can be large, print it modulo 998244353.

Input

The first line contains two integers n,m. (1≤m,n≤5⋅10⁴)

The second line contains n integers a₁ ,⋯,a_n. (0≤a_i≤10⁵, $\sum\limits_{i = 1}^{n}a_i≤10^5$)

Output

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

Example input

4 6
0 1 2 3

Example output

0
0
9
96
500
1800

题解

快速幂、乘法逆元、组合数

题目大意，给你 n 种糖果以及每种糖果的数量，现在要将糖果全部分发给 k 个队伍，每个队伍可以获得不同种的糖果，但是每个队伍每种糖果只能有一个，问当 k = 1-m 时，对应的有多少种分法？

显然，读完题后就可以知道，此题的答案即为 $\prod\limits_{i = 1}^{n}C(_{m}^{a[i]})$ ，此外还要注意，当队伍组别小于 最大数量的糖果种类(代码中mv) 的数量时，是不能分配成功的，则直接输出 0 即可。

对于此题，需要注意优化。由于 $\sum\limits_{i = 1}^{n}a_i≤10^5$ ，则可以知道，最多只有 $\sqrt{10^5}$ 种不同的数量的糖果，将其归类处理，只要算出该组的一个组合数，再使用快速幂即可得出整个组别的累乘结果。

而在使用组合数的时候，会频繁用到阶乘，可以先预处理出，降低复杂度。同时，还会出现除法求余的情况，则由费马小定理可知，$a / b \equiv a*x(\mod{p})$ ，用其乘法逆元代替除法。，同时，也可在外先进行预处理，一降低复杂度。

时间复杂度：$O(m\times \sqrt{10^5} \times \log_{2}^{n})$

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 5e4 + 5, MOD = 998244353;
typedef long long LL;
int n, m;
int invp[N], p[N];
map<int, int> cnt;

//快速幂
int qpow(int a, int n) {
    int s = 1;
    while (n) {
        if (n & 1) s = s * 1ll * a % MOD;
        a = a * 1ll * a % MOD;
        n >>= 1;
    }
    return s;
}

//预处理出阶乘和逆元阶乘
void pre(int n) {
    p[0] = 1;
    invp[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * 1ll * i % MOD;
        invp[i] = invp[i - 1] * 1ll * qpow(i, MOD - 2) % MOD;
    }
}

//组合数
int C(int n, int m) {
    if (n == m) return 1;
    if (n - m < m) m = n - m;

    int ans = 1;
//    for (int i = n; i >= n - m + 1; i--) ans = ans * 1ll * i % MOD;
    ans = ans * 1ll * p[n] % MOD;
//    for (int i = 2; i <= m; i++) ans = ans * 1ll * inv[i] % MOD;
    ans = ans * 1ll * invp[m] % MOD;
    ans = ans * 1ll * invp[n - m] % MOD;
    return ans;
}

int main() {
    cin >> n >> m;
    int mv = 0;		//数量最大的种类的数量
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x) cnt[x]++;
        mv = max(mv, x);
    }

    for (int i = 1; i <= min(mv - 1, m); i++) puts("0");

    pre(m + 1);
    for (int i = min(mv, m + 1); i <= m; i++) {
        int ans = 1;
        for (auto &t:cnt) {
            int s = C(i, t.first);
            ans = ans * 1ll * qpow(s, t.second) % MOD;
        }
        printf("%d\n", ans);
    }

    return 0;
}