「2021-10-06 联考」抽卡

题目链接

题意

$n$ 个物品，每个时刻都恰好出现一个物品，有 $p_i$ 的概率出现 $i$。

记物品 $i$ 第一次出现时间为 $t_i$，求 $t$ 的平均数 $\overline t$ 与方差 $\sigma^2$ 的期望。

思路

对于平均数，显然 $E(\overline t)=\frac1n\sum_{i=1}^n\frac1{p_i}$。

根据方差公式 $\sigma^2=\frac1n\sum_{i=1}^nt_i^2-\overline t^2$，得：

$E(\sigma^2)=\frac{n-1}{n^2}\sum_{i=1}^nE(t_i^2)-\frac2{n^2}\sum_{i=1}^n\sum_{j=i+1}^nE(t_it_j)$

转换成求 $E(t_i^2)$ 和 $E(t_it_j)$。

$\begin{aligned} E(t^2)&=\sum_{i=0}^{+\infty}(1-p)^i\cdot p\cdot(i+1)^2\\ &=\sum_{i=0}^{+\infty}(1-p)^i\cdot p\cdot i^2+\sum_{i=0}^{+\infty}(1-p)^i\cdot p\cdot(2i+1)\\ &=(1-p)\sum_{i=1}^{+\infty}(1-p)^{i-1}\cdot p\cdot i^2+p\sum_{i=0}^{+\infty}(1-p)^i\cdot(2i+1)\\ &=(1-p)E(t^2)+p\sum_{i=0}^{+\infty}(1-p)^i\cdot(2i+1)\\ &=\sum_{i=0}^{+\infty}(1-p)^i\cdot(2i+1)\\ &=\frac1p+2\sum_{i=0}^{+\infty}(1-p)^ii \end{aligned}$

记 $s=\sum_{i=0}^{+\infty}(1-p)^ii$，则 $s-(1-p)s=\sum_{i=1}^{+\infty}(1-p)^i=\frac1p-1$，所以 $s=\frac{\frac1p-1}p=\frac1{p^2}-\frac1p$。

代回原式：$E(t^2)=\frac{1-p}{p^2}$。

对于 $E(t_it_j)$，考虑 $2E(t_it_j)=E^2(t_i)+E^2(t_j)-E\left((t_i-t_j)^2\right)$，转为求 $E\left((t_i-t_j)^2\right)$。

这是求 $i,j$ 中出现一个后另一个期望再过多久出现。显然 $i$ 比 $j$ 先出现的概率为 $\frac{p_j}{p_i+p_j}$，由此可得：

$\begin{aligned} E\left((t_i-t_j)^2\right)&=\frac{p_i}{p_i+p_j}E(t_i^2)+\frac{p_j}{p_i+p_j}E(t_j^2)\\ &=\frac{p_iE(t_i^2)+p_jE(t_j^2)}{p_i+p_j} \end{aligned}$

实现

暴力枚举 $i,j$ 求 $E(t_it_j)$ 的时间复杂度是 $\mathcal O(n^2\log n)$，统一预处理逆元后是 $\mathcal O(n^2)$ 的。

然而 Early 并没有预处理逆元。

代码

#include<cstdio>
#include<cctype>
#include<numeric>
using namespace std;
const int N=5000,mod=998244353;
int n,p[N+1];
int Et[N+1],Et2[N+1];
int Eave,Evar;
int pow(int x,int t)
{
    int r=1;
    while(t) {
        if(t&1) {
            r=1ll*r*x%mod;
        }
        t>>=1,x=1ll*x*x%mod;
    }
    return r;
}
inline int inv(int x)
{
    return pow(x,mod-2);
}
int main()
{
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&p[i]);
    }
    for(int i=1,id=inv(accumulate(p+1,p+n+1,0ll)%mod);i<=n;++i) {
        p[i]=1ll*p[i]*id%mod;
    }
    for(int i=1;i<=n;++i) {
        Et[i]=inv(p[i]);
        Et2[i]=1ll*(2-p[i])*inv(1ll*p[i]*p[i]%mod)%mod;
    }
    Eave=accumulate(Et+1,Et+n+1,0ll)%mod*inv(n)%mod;
    int coef1=0,coef2=0;
    for(int i=1;i<=n;++i) {
        coef1=(coef1+Et2[i])%mod;
    }
    coef1=1ll*coef1*(n-1)%mod*inv(n*n)%mod;
    for(int i=1;i<n;++i) {
        for(int j=i+1;j<=n;++j) {
            coef2=(coef2+(1ll*p[i]*Et2[i]+1ll*p[j]*Et2[j])%mod*inv(p[i]+p[j]))%mod;
        }
    }
    coef2=1ll*coef2*inv(n*n)%mod;
    Evar=(coef1-coef2)%mod;
    printf("%d\n%d\n",(Eave+mod)%mod,(Evar+mod)%mod);
    return 0;
}