LINK

单独考虑每一类颜色糖果的期望即可

比如当选出 k k k个糖果时,第 i i i类糖果有 x i x_i xi​个

那么没有选到这类糖果的概率是 ∏ j = 0 k − 1 n − j − x i n − j \prod\limits_{j=0}^{k-1}\frac{n-j-x_i}{n-j} j=0∏k−1​n−jn−j−xi​​,选到的概率取个反即可

设共有 w w w类糖果,选出 k k k个的期望颜色数就是

∑ i = 1 w ( 1 − ∏ j = 0 k − 1 n − j − x i n − j ) \sum\limits_{i=1}^w(1-\prod\limits_{j=0}^{k-1}\frac{n-j-x_i}{n-j}) i=1∑w​(1−j=0∏k−1​n−jn−j−xi​​)

化简一下就是

w + ∑ i = 1 w ( ( n − x i ) ! ( n − x i − k ) ! ∗ ( n − k ) ! n ! ) w+\sum\limits_{i=1}^w(\frac{(n-x_i)!}{(n-x_i-k)!}*\frac{(n-k)!}{n!}) w+i=1∑w​((n−xi​−k)!(n−xi​)!​∗n!(n−k)!​)

w + ∑ i = 1 w ( ( n − x i ) ! ( n − x i − k ) ! ∗ ( n − k ) ! n ! ) w+\sum\limits_{i=1}^w(\frac{(n-x_i)!}{(n-x_i-k)!}*\frac{(n-k)!}{n!}) w+i=1∑w​((n−xi​−k)!(n−xi​)!​∗n!(n−k)!​)

对于每个 k k k单独计算需要花 O ( w ) O(w) O(w)的时间,最坏总复杂度为 O ( n 2 ) O(n^2) O(n2)

但是观察到 x i x_i xi​最多只有不多于 n \sqrt n n ​种取值,我们只需要把每种取值的结果算出来,乘以这种取值的糖果类型数即可,这样每个 k k k只需要 n \sqrt n n ​的时间即可计算

这样总体复杂度降低到 n n n\sqrt n nn ​

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int maxn = 5e5+10;
int n,c[maxn],a[maxn],shu[maxn],fac[maxn],inv[maxn];
map<int,int>mp1,mp2;
int quick(int x,int n)
{
	int ans = 1;
	for( ; n ; n>>=1,x=x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans;
}
int get(int zi,int mu){ return fac[zi]*inv[mu]%mod; }
void init()
{
	fac[0] = 1; inv[0] = 1;
	for(int i=1;i<=500000;i++)
	{
		fac[i] = fac[i-1]*i%mod;
		inv[i] = quick( fac[i],mod-2 )%mod;
	}
}
signed main()
{
	init();
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int x; cin >> x;
		mp1[x]++;//统计每种颜色的个数 
	}
	for(auto v:mp1 )	mp2[v.second]++;//记录有x个糖果的颜色类型有几种 
	for(int k=1;k<=n;k++)
	{
		int ans = 0;
		for(auto v:mp2 )
		{
			int val = 1;
			if( v.first+k>n )	val = 1;
			else
			{
				int r = get( n-v.first,n-v.first-k )*get( n-k,n )%mod;
				val = ( 1-r )%mod;
			}
			ans = ( ans+val*v.second%mod )%mod;
		}
		ans = ( ans%mod+mod )%mod;
		cout << ans << "\n";
	}
	return 0;
}

更多文章请关注《万象专栏》