「ABC215G」 Colorful Candies 2

题意概括

有 \(n\) 个糖果，每种都有一个颜色 \(c_i\)，求对于所有 \(k\in [1,n]\)，求出 \(C_n^k\) 种方案中糖果种类的期望数，对 \(998244353\) 取模。

分析

通过期望的定义，设 \(vis_i\) 表示每种颜色有没有被选，颜色总数为 \(m\)，则期望为 \(E(\sum\limits_{j=1}^{m}vis_j)\)，由线性期望的性质，\(E(\sum\limits_{j=1}^{m}vis_j)=\sum\limits_{j=1}^{m}E(vis_j)\)。

因为一个颜色的期望为：出现的方案数/总方案数=(总方案数-未出现的方案数)/总方案数，设每种颜色的总数为 \(cnt_j\)，所以 \(E(vis_j)=\frac{C_{n}^{k}-C_{n-cnt_j}^{k}}{C_n^k}\)。

可以把 \(c\) 数组离散化，再计算 \(cnt\)，因为 \(\sum\limits_{i=1}^{m}cnt_i=n\)，可把式子转化成 \(m_{max}(m_{max}+1)=2n\)，所以 \(m\) 严格小于 \(\sqrt n\)，总时间复杂度在 \(O(n\sqrt n)\) 级别。

因为空间足够，且调用次数较多，预处理出 \(1\sim n\) 的阶乘和逆元，用于 \(O(1)\) 求解组合数。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod=998244353;
ll n,m,c[50005],b[50005],col[50005],cnt[50005],jc[50005],inv[50005];
inline ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
inline void init(ll x){
    jc[0]=1;
    for(ll i=1;i<=x;++i){
        jc[i]=jc[i-1]*i%mod;
    }
    inv[x]=qpow(jc[x],mod-2);
    for(ll i=x-1;i>=0;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
inline ll C(ll n,ll m){
    if(m<0||n<m)return 0;
    return jc[n]*inv[n-m]%mod*inv[m]%mod;
}
map<ll,ll>mp1,mp2;
signed main(){
    cin>>n,init(n);
    for(ll i=1;i<=n;++i)cin>>c[i],mp1[c[i]]++;
    for(auto i:mp1)mp2[i.second]++;
    for(auto i:mp2)c[++m]=i.first,cnt[m]=i.second;
    for(ll i=1;i<=n;++i){
        ll ans=0;
        for(ll j=1;j<=m;++j){
            ans=(ans+(C(n,i)-C(n-c[j],i)+mod)%mod*cnt[j]%mod)%mod;
        }
        ans=ans*qpow(C(n,i),mod-2)%mod;
        cout<<ans<<'\n';
    }
    return 0;
}