CCPC 2021 Weihai - G. shinyruo and KFC (combination number, tips)

G. Shinyruo and KFC

The question
Altogether $n$ Kind of food , Each food has $a_i$ individual . The total number of food should not exceed $10^5$.
Now I want to share these foods with $k$ personal , Everyone can take many things , But each kind of food takes at most 1 individual .
about $k$ from 1 To $m$, Output the food distribution plan separately .
Answer model $998244353$.
$1\le m,n\le 5\cdot 10^4$
$0\le a_i\le 10^5,{\sum }_{i=1}^n{a}_i\le 10^5$

Ideas
Common to one food $a_i$ individual , among $k$ personal , Each person can get one at most , Then the distribution scheme is $C(k,ai)$.
that n Kind of food , among k The overall personal distribution plan is ：${\prod }_{i=1}^{n}C(k,a_i)$;
Re traversal m personal , In this case, the minimum time complexity is O(n * m), Overtime .

And the title says ai The total does not exceed 1e5, that ai The number of species is $\sqrt{1e5}$ Level , For repetition, use fast power to find power .
Preprocess the inverse element to find the combination number .

In this way, the time complexity is reduced to ：$O(m\sqrt{n}logn)$

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long
#define fi first
#define se second
#define endl '\n'
map<int,int> mp;

const int N = 200010, mod = 998244353;
int T, n, m;
int a[N];
struct node{
    
	int x, cnt;
}b[N];
int fac[N], inv[N], finv[N];

int qmi(int x, int y)
{
    
	int ans = 1;
	while(y)
	{
    
		if(y & 1) ans = ans * x % mod;
		x = x*x % mod;
		y >>= 1;
	}
	return ans;
}

void init(){
    
	fac[0]=inv[0]=inv[1]=finv[0]=finv[1]=1ll;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
	for(int i=2;i<N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<N;i++)finv[i]=finv[i-1]*inv[i]%mod;
}

inline int C(int a,int b){
    
	if(b>a)return 0;
	else return fac[a]*finv[a-b]%mod*finv[b]%mod;
}

signed main(){
    
	Ios;
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i], mp[a[i]]++;
	
	int cnt = 0;
	for(auto it : mp)
	{
    
		cnt++;
		b[cnt] = {
    it.first, it.second};
	}
	
	init();
	
	for(int i=1;i<=m;i++)
	{
    
		int ans = 1;
		for(int j=1;j<=cnt;j++)
		{
    
			ans = ans * qmi(C(i, b[j].x), b[j].cnt) % mod;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Experience

• If n The sum of the numbers does not exceed m, Then the number of types of these numbers is $\sqrt{m}$ Level .