[ABC215G] Colorful Candies 2

A6n6d6y6 · 2024-02-05 14:29:30 · 题解

前言

传送门

做之前：在刷概率与期望题目。欸？怎么这道题还没刷？

做当中：思路知道了，写好代码：怎么TLE了 ？？？

做之后：原来还能这么做题。

正文

言归正传，糖果的贡献显然与颜色无关，只与每种颜色的个数有关。

首先离散化，设一共有 m 中不同的颜色，离散化后为 1,2,3,\cdot\cdot\cdot,m。设 c_i 为颜色为 i 的糖果数量。

依次考虑每次选择 k 个糖果：定义离散型随机变量 x_i=1/0 表示第 i 种类的糖果选/不选。那么期望为 E(\sum\limits_{i=1}^m x_i)=\sum\limits_{i=1}^mE(x_i)（和的期望等于期望的和）。

显然，一个颜色出现的期望为：E(x_i)=\dfrac{C_n^k-C_{n-c_i}^k}{C_n^k}。

如果直接枚举 i,k，时间复杂度为 O(n^2)。考虑优化。

优化：如果有 t 种颜色的糖果，数量均为 c_i，则只需计算 t\times E(x_i)。设 c 中不同颜色糖果有 b 种，而 \sum\limits_{i=1}^mc_i=n，所以 b 的上界显然为 \sqrt n。

坑点

• 不能每次都用费马小定理求逆元，这样时间复杂度是 O(n\sqrt n\log n)。需要预处理从 1 到 n 的逆元，这样时间复杂度为 O(n\sqrt n)；
• 时限 4 秒，但注意你的常数，否则你就会这样（就差0.1秒）。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int x=0;char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x;
}//卡常快读
void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}//卡常快写
const int maxn=5e4+10,mod=998244353;
int n,m,T,ans,a[maxn],c[maxn],f[maxn],g[maxn];
unordered_map<int,int>lsh,cnt;
int ksm(int x,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*x%mod;
        x=x*x%mod,b>>=1;
    }
    return ans;
}//快速幂
int inv(int x){
    if(x<=5e4)return g[x];//如果预处理过就返回预处理后的值
    return ksm(x,mod-2);//否则直接算
}
int C(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return f[x]*inv(f[y]*f[x-y]%mod)%mod;
}//组合数
signed main(){
    f[0]=1;for(int i=1;i<=5e4;i++)f[i]=f[i-1]*i%mod;
    for(int i=1;i<=5e4;i++)g[i]=ksm(i,mod-2);//预处理
    n=read();
    for(int i=1;i<=n;i++)lsh[a[i]=read()]++;
    for(auto i:lsh)cnt[i.second]++;
    for(auto i:cnt)m++,a[m]=i.first,c[m]=i.second;//离散化+统计出现次数
    for(int k=1;k<=n;k++){
        ans=0;
        for(int j=1;j<=m;j++)
            ans=(ans+(C(n,k)-C(n-a[j],k)+mod)%mod*c[j]%mod)%mod;
        ans=ans*inv(C(n,k))%mod;
        write(ans);putchar('\n');//计算并输出
    }
    return 0;
}

AC记录，极限数据3.96秒爬过去的。