ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【ICPC】The 2021 CCPC Weihai Onsite G [打印本页]

---

作者: 滴水恩情    时间: 2024-10-15 23:03
标题: 【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                              n                  n kinds of foods in KFC, and he plans to order                                              a                            i                                       a_i                  ai​ number of the                                    i                              i                  i-th food for every                                    i                         ∈                         [                         1                         ,                         n                         ]                              i \in [1,n]                  i∈[1,n]. Due to shortage of manpower, the total number of all kinds of foods is no larger than                                    1                                   0                            5                                       10^5                  105.
After the competition, he will hand all the KFC out to                                    k                              k                  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                         ,                         ⋯                          ,                         m                              k=1,2,\cdots,m                  k=1,2,⋯,m.
As the answer can be large, print it modulo                                    998244353                              998244353                  998244353.
输入格式

The first line contains two integers                                    n                         ,                         m                              n,m                  n,m. (                                   1                         ≤                         m                         ,                         n                         ≤                         5                         ⋅                         1                                   0                            4                                       1 \le m,n \le 5 \cdot 10^4                  1≤m,n≤5⋅104)
The second line contains                                    n                              n                  n integers                                              a                            1                                  ,                         ⋯                          ,                                   a                            n                                       a_1,\cdots,a_n                  a1​,⋯,an​. (                                   0                         ≤                                   a                            i                                  ≤                         1                                   0                            5                                  ,                                                             ∑                                       i                               =                               1                                      n                                            a                            i                                  ≤                         1                                   0                            5                                       0\le a_i\le 10^5,\ \sum_{i=1}^n a_i\le 10^5                  0≤ai​≤105, ∑i=1n​ai​≤105)
输出格式

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

样例输入 #1

1. 4 6
2. 0 1 2 3

复制代码

样例输出 #1

1. 0
2. 0
3. 9
4. 96
5. 500
6. 1800

复制代码

解法

解题思绪

轻易发现，队伍人数                                    >                                              max                               ⁡                                                 i                               =                               1                                                 i                               ≤                               n                                                      a                            i                                       > \max_{i=1}^{i\leq n}a_i                  >maxi=1i≤n​ai​ 时，一定无解，因为根据鸽巢定理，每个人肯定被分到重复的糖果。
轻易发现，答案其实就是                                             ∑                                       j                               =                               m                               a                                           x                                                             a                                        i                                                  +                                     1                                                                        j                               ≤                               n                                                      ∑                                       i                               =                               1                                                 i                               ≤                               n                                                      C                            j                                       a                               i                                                 \sum_{j=max_{a_i+1}}^{j\leq n} \sum_{i=1}^{i\leq n}C_{j}^{a_i}                  ∑j=maxai​+1​j≤n​∑i=1i≤n​Cjai​​，但是思量到                                   i                         ≤                         5                         ∗                         1                                   0                            4                                       i \leq 5*10^4                  i≤5∗104，直接枚举会超时。
由于                                   0                         ≤                                   a                            i                                  ≤                         1                                   0                            5                                  ,                                                             ∑                                       i                               =                               1                                      n                                            a                            i                                  ≤                         1                                   0                            5                                       0\le a_i\le 10^5,\ \sum_{i=1}^n a_i\le 10^5                  0≤ai​≤105, ∑i=1n​ai​≤105，所以                                             a                            i                                       a_i                  ai​的种类至多有                                             n                                       \sqrt n                  n            ​种，那么我们可以利用一个                                   m                         a                         p                              map                  map来存储类型的个数，利用快速幂加快组合数的计算即可。
由于                                             a                            i                                  ≤                         1                                   0                            5                                       a_i \leq 10^5                  ai​≤105，我们可以预处理出所有的阶乘，然后利用组合数的公式即可。
末了复杂度为                                   O                         (                         m                                   n                                  l                         o                                   g                            2                                  n                         )                              O(m\sqrt n log_2 n)                  O(mn            ​log2​n)
代码

1. const int N = 1e6 + 10;
2. namespace CNM {
3.         const int N = 3e5 + 5;
4.         int quick(int x, int n) {
5.                 x %= mod;
6.                 int res = 1;
7.                 while (n) {
8.                         if (n & 1) res = (res * x) % mod;
9.                         x = x * x % mod;
10.                         n >>= 1;
11.                 }
12.                 return res;
13.         }
14.         int inv(int x) {
15.                 return quick(x, mod - 2);
16.         }
17.         int fac[N], invfac[N];
18.         void init() {
19.                 fac[0] = 1;
20.                 for (int i = 1; i < N; ++i) {
21.                         fac[i] = (fac[i - 1] * i) % mod;
22.                 }
23.                 invfac[N - 1] = inv(fac[N - 1]);
24.                 for (int i = N - 2; i >= 0; --i) {
25.                         invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
26.                 }
27.         }
28.         int C(int n, int m) {
29.                 if (n < m || m < 0) return 0;
30.                 return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
31.         }
32. }
34. using namespace CNM;
36. void solve() {
37.         int n, m;
38.         cin >> n >> m;
39.         map<int, int>mp;
40.         vector<int>a(n + 1);
41.         for (int i = 1; i <= n; ++i) {
42.                 cin >> a[i];
43.                 mp[a[i]]++;
44.         }
45.         int maxx = *max_element(a.begin() + 1, a.end());
47.         init();
49.         vector<int>prefix(n + 1);
51.         sort(a.begin() + 1, a.end());
52.        
53.         vector<int>res(m + 1);
54.         for (int i = 1; i <= m; ++i) {
55.                 if (i < maxx) {
56.                         res[i] = 0;
57.                         continue;
58.                 }
60.                 int t1 = quick(fac[i],n) % mod;
61.                
62.                 int t2 = 1;
63.                 for (auto& [x, y] : mp) {
64.                         t2 *= quick((fac[x] * fac[i - x] % mod), y) % mod;
65.                         t2 %= mod;
66.                 }
68.                 int ans = t1 * inv(t2) % mod;
70.                 res[i] = ans;
71.         }
73.         for (int i = 1; i <= m; ++i) {
74.                 cout << res[i] << "\n";
75.         }
77. }
79. signed main() {
80.         ios::sync_with_stdio(0);
81.         std::cin.tie(0);
82.         std::cout.tie(0);
83.         int t = 1;
84.         //cin >> t;
85.         while (t--) {
86.                 solve();
87.         }
88. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4