主要思路

好难理解啊这题，让我想想。

首先，我们要把这个问题搞成一个二元问题，可以枚举最后的颜色，然后来单独计算。考虑最后的颜色为白色，其他颜色是黑色。转换成这个问题后，可以考虑进行转移。

首先，一个状态可以直接被白色颜色数量 \(x\) 所刻画。在 \(x\) 的状态下，发现有 \(x(n – x)\) 种方案是会导致颜色数量出现变动，那么变动的概率就是 \(g_x = \frac{x(n – x)}{n(n – 1)}\)，变动的期望次数也就是 \(\frac{1}{g_x}\)（因为 \(x\) 是不变的）。变动时，\(x += 1\) 和 \(x -= 1\) 的概率一致（因为反过来就可以一一对应）。

那么，如果我们只考虑这个二元问题，设 \(f_x\) 为全部变成白色的期望步数，可以得到：

\[ f_x = \frac{f_{x – 1} + f_{x + 1}}{2} + g_x \]

看上去有个环，但是我们发现一个特点：边界时，当 \(x = 0, x = n\) 时，\(f_x\) 为 \(0\)。那么，来到 \(f_1 = \frac{f_2}{2} + g_1\)，得 \(f_2 = 2f_1 – 2g_1\)。发现这样递推下去，每个 \(f_x\) 都可以被表示为 \(f_x = af_1 + b\) 的形式（有点类似于树上高斯消元）。当递推到 \(f_n\) 时，就可以往回推了。

然而，得到这个之后仍然不是最终答案，他只是这个二元问题的答案。要计算最后的综合概率，我们还需要加上条件，也就是钦定最终一定是某种颜色。我们只需要乘上一个 \( \frac{cnt}{n} \) 即可。

代码

// BZ2554.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4 + 200;

int n, cnt[26];
char str[MAX_N];
double ai[MAX_N], bi[MAX_N], f[MAX_N], g[MAX_N], ans;

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1);
    for (int i = 1; i <= n; i++)
        cnt[str[i] - 'A']++;
    for (int i = 1; i <= n; i++)
        g[i] = 1.0 * i / n;
    ai[1] = 1, bi[1] = 0;
    for (int i = 1; i < n; i++)
    {
        ai[i + 1] = (ai[i] - ai[i - 1] * (i - 1) / (2 * i)) * (2 * i) / (i + 1);
        bi[i + 1] = (bi[i] - bi[i - 1] * (i - 1) / (2 * i) - double(n * (n - 1)) / double(2 * i * (n - i))) * (2 * i) / (i + 1);
    }
    f[1] = -bi[n] / ai[n];
    for (int i = 0; i < 26; i++)
        ans += g[cnt[i]] * (ai[cnt[i]] * f[1] + bi[cnt[i]]);
    printf("%.1lf\n", ans);
    return 0;
}