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=1nai≤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
解法
解题思绪
轻易发现，队伍人数 > max i = 1 i ≤ n a i > \max_{i=1}^{i\leq n}a_i >maxi=1i≤nai 时，一定无解，因为根据鸽巢定理，每个人肯定被分到重复的糖果。
轻易发现，答案其实就是 ∑ 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+1j≤n∑i=1i≤nCjai，但是思量到 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=1nai≤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 log2n)
代码
- 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();
- }
- };
|
