题解 P5516 【[MtOI2019]小铃的烦恼】

· · 题解

感觉对我这种数学萌新来说，这是一道很好的期望题。。

答案

设答案的期望为 E[X]，其中 X 为步数的随机变量，若设 Y 为最后字符的随机变量，则由全期望公式：

E[X]=E[E[X|Y]]=\sum_{y=1}^{\sum} P(y=Y)E[X|Y=y]

概率

假设当前字符为 y，出现次数为 i，若设 OPT 为此次操作的随机变量，则由全概率公式，

& =\frac{i(i-1)+(n-i)(n-i-1)}{n(n-1)}P_i(Y=y)+\frac{i(n-i)}{n(n-1)}(P_{i+1}(Y=y)+P_{i-1}(Y=y)) \end{aligned}

化简得 P_i(Y=y)=\frac{P_{i-1}(Y=y)+P_{i+1}(Y=y)}{2}，发现是等差数列，由于 P_0(y=Y)=0, P_n(Y=y)=1，故 P_i(Y=y)=\frac{i}{n}。

期望

令 T 为 Y=y 这个事件，即最后的字符是 y。

设 E_i[X|T] （事实上，这个下标 i，只是表示我们在不同的样本空间里罢了）表示最后字符为 y，当前这种字符有 i 个，步数的期望。这是条件期望。若设 OPT|T 为此次操作的随机变量（当然，是在事件 T 发生的大前提下），则由全期望公式，

& = 1+\sum_{opt} \frac{P_i(OPT=opt,T)}{P(T)} E_{next(i,OPT)}[X|T] \\ \end{aligned}

（第 3 步使用条件概率公式）

（重要） P_i(OPT=opt,T) 是什么？它的意思是做完这个操作后这个字符能作为最后字符，这两部分是独立的，所以是 P(OPT=opt)\times \frac{next(i,OPT)}{n}。

因此，上式化为

E_i[X|T]=1+\frac{i(n-i)}{n(n-1)} \frac{i-1}{i} E_{i-1}[X|T]+\frac{i(n-i)}{n(n-1)} \frac{i+1}{i} E_{i+1}[X|T]+\left(1 - \frac{2i(n-i)}{n(n-1)} \right) E_i[X|T]

故而

E_i[X|T]=\frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}E_{i-1}[X|T]+\frac{i+1}{2i}E_{i+1}[X|T]

实现

设 f_i=E_i[X|T]，则 f_i=\frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}f_{i-1}+\frac{i+1}{2i}f_{i+1}。边界 f_0=?, f_n=0。（f_0 是未定义的，但没关系，因为 f_1 的式子中 f_0 的系数是 0）。

答案为 \sum\limits_{i=1}^{\sum} \frac{cnt_i}{n} f_{cnt_i}。

现在的问题是求出 f_i，我们待定 f_{n-1}，将所有数都表示为关于 f_{n-1} 的一次函数，此时还未使用 f_1 的式子，用它来算出 f_{n-1} 的值即可。

时间复杂度 O(n)。

我未解决的问题

样本空间是什么？如果说是操作序列的话，样本空间岂不就是无限集？

算了算了，非要纠结样本空间是什么的话，有些东西反而不太好说了。。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
int N, buc[30]; char S[MAXN]; double f[MAXN], a[MAXN], b[MAXN], ans;
int main() {
    scanf("%s", S + 1), N = strlen(S + 1); int i;
    for (i = 1; i <= N; ++i) ++buc[S[i] - 'A'];
    a[N - 1] = 1;
    for (i = N - 1; i >= 2; --i) {
        a[i - 1] = a[i] * 2 * i / (i - 1) - a[i + 1] * (i + 1) / (i - 1),
        b[i - 1] = b[i] * 2 * i / (i - 1) - b[i + 1] * (i + 1) / (i - 1) - (double)N * (N - 1) / (ll)((i - 1) * (N - i));
    }
    f[N - 1] = (N / 2.0 + b[2] - b[1]) / (a[1] - a[2]);
    for (i = 1; i <= N - 2; ++i) f[i] = a[i] * f[N - 1] + b[i];
    for (i = 0; i < 26; ++i) ans += f[buc[i]] * buc[i] / N;
    printf("%.1f\n", ans);
    return 0;
}