【ICPC】The 2021 CCPC Weihai Onsite G

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

样例输入 #1

4 6
0 1 2 3

样例输出 #1

0
0
9
96
500
1800

解法

解题思路

容易发现，队伍人数 $>{\max }_{i=1}^{i\le n}{a}_i$ 时，一定无解，因为根据鸽巢定理，每个人必定被分到重复的糖果。

容易发现，答案其实就是${\sum }_{j=ma{x}_{a_i+1}}^{j\le n}{\sum }_{i=1}^{i\le n}{C}_j^{a_i}$，但是考虑到$i\le 5\ast 10^4$，直接枚举会超时。

由于$0\le a_i\le 10^5,{\sum }_{i=1}^n{a}_i\le 10^5$，所以$a_i$的种类至多有$\sqrt{n}$种，那么我们可以使用一个$map$来存储类型的个数，使用快速幂加快组合数的计算即可。

由于$a_i\le 10^5$，我们可以预处理出所有的阶乘，然后使用组合数的公式即可。

最后复杂度为$O(m\sqrt{n}lo{g}_{2}n)$

代码

const int N = 1e6 + 10;
namespace CNM {const int N = 3e5 + 5;int quick(int x, int n) {x %= mod;int res = 1;while (n) {if (n & 1) res = (res * x) % mod;x = x * x % mod;n >>= 1;}return res;}int inv(int x) {return quick(x, mod - 2);}int fac[N], invfac[N];void init() {fac[0] = 1;for (int i = 1; i < N; ++i) {fac[i] = (fac[i - 1] * i) % mod;}invfac[N - 1] = inv(fac[N - 1]);for (int i = N - 2; i >= 0; --i) {invfac[i] = (invfac[i + 1] * (i + 1)) % mod;}}int C(int n, int m) {if (n < m || m < 0) return 0;return fac[n] * invfac[m] % mod * invfac[n - m] % mod;}
}using namespace CNM;void solve() {int n, m;cin >> n >> m;map<int, int>mp;vector<int>a(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];mp[a[i]]++;}int maxx = *max_element(a.begin() + 1, a.end());init();vector<int>prefix(n + 1);sort(a.begin() + 1, a.end());vector<int>res(m + 1);for (int i = 1; i <= m; ++i) {if (i < maxx) {res[i] = 0;continue;}int t1 = quick(fac[i],n) % mod;int t2 = 1;for (auto& [x, y] : mp) {t2 *= quick((fac[x] * fac[i - x] % mod), y) % mod;t2 %= mod;}int ans = t1 * inv(t2) % mod;res[i] = ans;}for (int i = 1; i <= m; ++i) {cout << res[i] << "\n";}}signed main() {ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//cin >> t;while (t--) {solve();}
};