前言

期望的广义定义：一次随机抽样中所期望的某随机变量的取值。

一个例子：

一次考试满分 100pts100pts，有 0.50.5 的概率考 90pts90pts，0.30.3 的概率考 80pts80pts，0.20.2 的概率考 50pts50pts，则这次考试成绩的期望即为 0.5×90+0.3×80+0.2×50=79pts0.5\times 90+0.3\times 80+0.2\times 50=79pts。

与 加权平均值 类似。

P8774 爬树的甲壳虫

Problem Link

Statement

有一只甲壳虫想要爬上一颗高度为 nn 的树，它一开始位于树根，高度为 00，当它尝试从高度 i−1i-1 爬到高度为 ii 的位置时有 PiP_{i} 的概率会掉回树根，求它从树根爬到树顶时，每次尝试花费 11 个单位时间，求经过的时间的期望值是多少。

Solution

正推方法。

设 fif_i 表示从根爬到 ii 花费时间的期望。

考虑转移，如果尝试成功，可以直接花费 11 单位时间从 i−1i - 1 跳到 ii，期望为 (1−pi)×1(1 - p_{i})\times 1；如果尝试失败，需要花费 11 单位时间回到根，然后再花 fif_i 的时间回到 ii，期望为 pi×(fi+1)p_i\times (f_i + 1)。

容易得到 fi=fi−1+(1−pi)+(fi+1)×pif_i = f_{i - 1} + (1 - p_i) + (f_i + 1)\times p_i。化简后，可以得到下面的方程：

fi=fi−1+11−pi=(fi−1+1)×yiyi−xif_i = \frac{f_{i-1} + 1}{1 - p_i} = (f_{i - 1} + 1)\times\frac{y_i}{y_i - x_i}

比倒推简单许多。

Core Code

这是倒推的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

ll ksm(ll x,ll y) {//快速幂
    ll res=1;
    while(y) {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int main() {
    n=read();
    for(int i=1;i<=n;i++) {
        int a=read(),b=read();
        p1[i]=a*ksm(b,mod-2)%mod;//失败概率
        p2[i]=(b-a)*ksm(b,mod-2)%mod;//成功概率
    }
    A=1;
    ll t=1;
    for(int i=1;i<=n;i++) {
        if(i!=n) A=(A+p2[i]*t%mod)%mod;
        B=(B+p1[i]*t%mod)%mod;
        t=(p2[i]*t)%mod;
    }
    write(A*ksm((1-B+mod)%mod,mod-2)%mod);
    return 0;
}

ABC360E Random Swaps of Balls

Luogu Link | AtCoder Link

Statement

有 nn 个球，其中 n−1n-1 球为白球，剩下一个球为黑球。初始时黑球为第 11 个球。

你可以进行 kk 次操作，每次操作等概率随机选择两个整数 i,j∈[1,n]i, j\in [1,n]，然后交换第 ii 个和第 jj 个球。

求最终黑球位置期望，对 P=998,244,353P=998,244,353 取模。

Solution

设 fif_i 为第 ii 次操作后的期望值，显然 f0=1f_0=1。

则有：

fi={1,i=0(n−1)2+1n2×fi−1+2n2×(n(n+1)2−fi−1),otherwise.f_i= \begin{cases} 1 &,i=0\\ \dfrac{(n-1)^2+1}{n^2}\times f_{i-1}+\dfrac{2}{n^2}\times (\dfrac{n(n+1)}{2}-f_{i-1}) &,\text{otherwise.} \end{cases}

可以将式子分为两部分：

• 第一部分加号前，表示在第 ii 次操作时球 xx 的位置没有被移动。此时选择的两数 a,ba,b 各有 n−1n-1 种选择，注意还有一种 a=b=xa=b=x 的情况，所以该情况概率为 (n−1)2+1n2\dfrac{(n-1)^2+1}{n^2}，再乘上该情况下 xx 的位置，即 fi−1f_{i-1}；
• 第二部分为加号后，表示在第 ii 次操作时移动了 xx 的位置。球落到每个位置上的概率显然是相等的 2n2\dfrac{2}{n^2}，期望显然为 ∑i=1n(2n2×i)\sum_{i=1}^n(\dfrac{2}{n^2}\times i)。但需要减去 xx 仍在操作前位置上的情况，注意由于不确定当前 xx 的位置，不能只使 i∈[2,n]i\in[2,n] 而是需要减掉 fi−1f_{i-1}。

Core Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int ksm(int x,int p) {
    int res=1;
    while(p>0) {
        if(p&1) res=res*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return res;
}
signed main() {
    n=read();k=read();
    f[0]=1;
    int n2=ksm((n*n)%mod,mod-2);
    int a=((n-1)*(n-1))%mod;
    int sum=((1+n)*n/2)%mod;
    for(int i=1;i<=k;i++) {
        f[i]=((a+1)*f[i-1]%mod*n2%mod+((2*n2%mod)*(sum-f[i-1])%mod)%mod+mod)%mod;
    }
    printf("%lld\n",f[k]); 
    return 0;
}

P1654 OSU!

Problem Link

Statement

给定 nn 次操作，每次操作有成功率 pip_i，成功记为 11，失败记为 00，形成一个长度为 nn 的 01 串。极长的连续 xx 个 11 贡献贡献 x3x^3 分数，求期望得分。

Solution

设 fif_i 为第 ii 次操作后的期望得分，f0=0f_0=0。

每次操作成功对答案的贡献为 (k+1)3−k3=3k2+3k+1(k+1)^3-k^3=3k^2+3k+1。

则通过递推求 k2k^2 和 kk 的期望即可，这里设为 len2len2 和 lenlen，要注意 E(k2)≠E(k)2E(k^2)\not =E(k)^2，所以 len2len2 和 lenlen 需要分别求。

则最终转移方程为：

leni=(leni−1+1)×pilen2i=(len2i+2×len2i−1+1)×pifi=fi−1+(3×len2i−1+3×leni−1+1)×pi\begin{aligned} len_i&=(len_{i-1}+1)\times p_i\\ len2_i&=(len2_i+2\times len2_{i-1}+1)\times p_i\\ f_i&=f_{i-1}+(3\times len2_{i-1}+3\times len_{i-1}+1)\times p_i \end{aligned}

这里还注意到最后一个式子与前两个不同。原因是前两个式子的含义是第 ii 位的期望，但最终要求的答案是前 nn 位的期望。

Core Code

1
2
3
4
5
6
7
8
9
10
11

int main() {
    n=read();
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) {
        len[i]=(len[i-1]+1.0)*p[i];
        len2[i]=(len2[i-1]+2.0*len[i-1]+1.0)*p[i];
        f[i]=f[i-1]+(3.0*len2[i-1]+3.0*len[i-1]+1.0)*1.0*p[i];
    }
    printf("%.1lf\n",f[n]);
    return 0;
}

P1297 [国家集训队] 单选错位

Problem Link

Statement

nn 道题，第 ii 道有 aia_i 个选项，选择每个选项的概率第相等的。但是每个选择都会填到后一道题。求对的期望题数。

Solution

对于每一个题目 ii，其是否正确仅与 ii 和 i−1i-1 道题目选项个数有关。

要使 ii 和 i−1i-1 个题目选择的答案一样，仅有 min⁡(ai,ai−1)\min(a_i,a_{i-1}) 种情况，而总共有 ai×ai−1a_i\times a_{i-1} 种情况。易证。

所以 fi=fi−1+min⁡(ai,ai−1)ai×ai−1f_i=f_{i-1}+\dfrac{\min(a_i,a_{i-1})}{a_i\times a_{i-1}}。

题目对内存要求严格，不能用数组保存答案。

Core Code

1
2
3
4
5

ans=1.0*min(a[1],a[n])/(a[1]*a[n]*1.0);
for(int i=2;i<=n;i++) {
    ans=ans+1.0*min(a[i-1],a[i])/(a[i-1]*a[i]*1.0);
}
printf("%.3Lf\n",ans);

P4550 收集邮票

Problem Link

Statement

有 nn 种不同的邮票，皮皮想收集所有种类的邮票。每次只能买一张，买到的邮票是等概率的。所以皮皮购买第 kk 次邮票需要支付 kk 元钱。

求得到所有种类的邮票需要花费的钱数目的期望。

Solution

设买了 kk 张邮票才能集齐，那么最终答案为 ∑i=1ki=k+k22\sum_{i=1}^ki=\dfrac{k+k^2}{2}。

所以我们设 fif_i 表示已经集齐了 ii 张邮票，还需要买的邮票数的期望。

因为有 in\dfrac{i}{n} 的概率买到已有的，那么此时次数应 +1+1；有 n−in\dfrac{n-i}{n} 的概率买到没有的，次数应在 fi+1f_{i+1} 的基础上 +1+1。

所以可得：

fi=in×(fi+1)+n−in×(fi+1+1)fi=infi+n−infi+1+1n−infi=n−infi+1+1fi=fi+1+nn−i\begin{aligned} f_i&=\dfrac{i}{n}\times(f_i+1)+\dfrac{n-i}{n}\times(f_{i+1}+1)\\ f_i&=\dfrac{i}{n}f_i+\dfrac{n-i}{n}f_{i+1}+1\\ \dfrac{n-i}{n}f_i&=\dfrac{n-i}{n}f_{i+1}+1\\ f_i&=f_{i+1}+\dfrac{n}{n-i} \end{aligned}

由于上文提到 E(k2)≠E(k)2E(k^2)\not =E(k)^2，所以需要根据 fif_i 完全平方展开预处理一个 gig_i：

gi=in×(fi+1)2+n−in×(fi+1+1)2⇒=gi+1+2in−ifi+2fi+1+nn−i\begin{aligned} g_i&=\dfrac{i}{n}\times(f_i+1)^2+\dfrac{n-i}{n}\times(f_{i+1}+1)^2\\ \Rightarrow&=g_{i+1}+\dfrac{2i}{n-i}f_i+2f_{i+1}+\dfrac{n}{n-i} \end{aligned}

由于 fif_i 依赖于 fi+1f_{i+1} 且已知 fn=0f_{n}=0，故使用倒推。最终答案 f0+g02\dfrac{f_0+g_{0}}{2}。

Core Code

1
2
3
4
5
6

n=read();
for(int i=n-1;i>=0;i--) {
    f[i]=f[i+1]+n*1.0/(n-i)*1.0;
    g[i]=g[i+1]+i*2.0/(n-i)*1.0*f[i]+2.0*f[i+1]+n*1.0/(n-i)*1.0;
}
printf("%.2lf\n",(f[0]+g[0])/2.0);

注：本文最初发表于 2023-05-27。