[数据结构与算法]2021 CCPC 威海赛区G题 Desserts

2021 CCPC 威海赛区G题 Desserts

题解

有$n$种类型的糖果（第$i$种糖果有$a_i$个）要分给$k(k=[1,m])$个队伍，每个队伍在同一种类型的糖果中只能拿出一个。

现在要将所有的糖果发完，求有多少种方案。

数据范围满足$n,m\le 5?10^4,{\sum }_{i=1}^n{a}_i\le 10^5$。

思路

先考虑暴力的做法，当需要分给$k$个队伍时，结果为${\prod }_{i=1}^n{C}_k^{a_i}$（从$k$个队伍中选出$a_i$个队分发第$i$种糖果），组合数可以做预处理。
暴力去枚举$k$时，复杂度为$O(m?n)$，会超时。

计算${\prod }_{i=1}^n{C}_k^{a_i}$时，如果将相同的$a_i$放在一起，答案就变成了${\prod }_{i=1}^{n^{\prime }}{(C_k^{a_i})}^{p_i}$。
例如：$C_k^1{C}_k^2{C}_k^2{C}_k^3{C}_k^3{C}_k^3=(C_k^1)(C_k^2{)}^2(C_k^3{)}^3$。

同时可以注意到题目中有一个条件是：${\sum }_{i=1}^n{a}_i\le 10^5$，那么$n^{\prime }$最大为$\sqrt{10^5}$。（想了半天也没想到这个条件可以这么用）
可以先预处理出来$p$，然后计算时使用快速幂，这样就可以确保复杂度可以通过题目。

AC的代码

#include <bits/stdc++.h>
#define ll long long
#define pub push_back
#define sz(x) (int)(x).size()
using namespace std;

const int mod = 998244353;
const int N = 1e5 + 10;

ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

ll inv(ll x) { return power(x, mod - 2); }

int n, m, a[N], p[N];
int vis[N];
ll fac[N], inv_f[N];

void init() {
    fac[0] = 1;
    for (int i = 1; i <= N - 10; i++) fac[i] = fac[i - 1] * i % mod;
    inv_f[N - 10] = inv(fac[N - 10]);
    for (int i = N - 11; i >= 0; i--) inv_f[i] = inv_f[i + 1] * (i + 1) % mod;
}

ll C(ll n, ll m) {
    if (m > n) return 0;
    return fac[n] * inv_f[m] % mod * inv_f[n - m] % mod;
}

int main() {
    init();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> vec;  // 最多sqrt(1e5)个
    for (int i = 1; i <= n; i++) {
        p[a[i]]++;
        if (vis[a[i]]) continue;
        vis[a[i]] = 1;
        vec.pub(a[i]);
    }

    for (int k = 1; k <= m; k++) {
        ll res = 1;
        for (auto it : vec) res = res * power(C(k, it), p[it]) % mod;

        cout << res << "\n";
    }

    return 0;
}