洛谷P5516 [MtOI2019] 小铃的烦恼题解

题目链接：P5516 [MtOI2019] 小铃的烦恼

题意：

小铃每天都会整理一次铃奈庵的书籍。这次桌子上有 $n$ 本魔法书，这些书一次排成一排，每本书有一个魔法属性和编号。

最开始这些书的魔法属性都是一样的，但是因为被人多次使用，魔法属性发生了变化，小铃想让所有书的魔法属性重新全部相同。

这次小铃找到了雾雨魔理沙(Kirisame Marisa)帮忙整理书籍，每次魔理沙可以释放选定魔法，魔法会随机选择两本书 $a,b$ ( $a$ 不等于 $b$ )。

选定这两本书后，魔理沙会释放转移魔法，使得有 $p_{a,b}\ \left(p_{a,b}\in (0,1]\right)$ 的概率，第 $b$ 本书的魔法属性变成第 $a$ 本书的魔法属性。也就是说有 $1-p_{a,b}$ 的概率，使得你即使选定了 $a,b$ 两本书，但是魔法属性的转移不成功，意味着这次操作是无效的 。

注意 $p_{a,b}$ 是对于转移是否成功的概率，和随机选择两本书的操作互不影响。

现在小铃想知道，求期望操作多少次，才能使所有的书魔法属性都一样？由于时间紧迫，小铃找到了你，希望你可以帮其解决这个问题，不然小铃就不会给你这题的分了。

输入格式：

第一行一个字符串，第 $i$ 个字符表示第 $i$ 本书的魔法属性，注意每本书的魔法属性为 $A$ 到 $Z$ 的所有的大写字母中的任意一字母。(设字符串的长度为 $n$ ) 。

第二行到第 $n+1$ 行，每行 $n$ 个实数，第 $i$ 行的第 $j$ 个数表示 $p_{i,j}$ 。

输出格式：

结果，精确到小数点后 $1$ 位。

数据范围：

$n\leq2\times 10^3,~\left(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{n}p_{a,b}\right) = n^2$ 。

毒瘤期望题。

首先因为 $p_{a,b} \in(0,1]$ 所以 $p_{a,b}=1$ 恒成立，也就是不用考虑 $p$ 了。

根据全期望公式

$\begin{aligned} \mathrm{E}(X) & =\mathrm{E}(\mathrm{E}(X \mid Y)) \\[8pt] & =\sum_y \mathrm{E}(X \mid Y=y) \cdot \operatorname{Pr}(Y=y) \end{aligned}$

显然这个 $\operatorname{Pr}(Y=y)$ 是可以 dp 的，即整个串变为 $y$ 的概率

因为字符只有 $26$ 种，所以我们不妨直接枚举 $y$ 。

记 $f_i$ 为字符 $y$ 的个数有 $i$ 个时 $s$ 变成 $y$ 的概率（$s$ 指题目给的字符串），则

$f_i=\frac{i(n-i)}{n(n-1)} f_{i-1}+\frac{i(n-i)}{n(n-1)} f_{i+1}+\left(1-\frac{2 i(n-i)}{n(n-1)}\right) f_i$

解一下方程

$f_i=\frac{f_{i-1}+f_{i+1}}{2}$

诶，这不就等差数列么，于是 $f_i = \frac{i}{n}$ 。不妨记为 $\mathrm{Pr}_i(Y=y)=f_i$ 。

接着考虑下式……吗？

$\begin{aligned} \mathrm{E}(X \mid Y=y) & =\sum_x x \cdot \operatorname{Pr}(X=x \mid Y=y) \\ & =\sum_x x \cdot \frac{\operatorname{Pr}(X=x, Y=y)}{\operatorname{Pr}(Y=y)} \end{aligned}$

好吧，可以发现这个 $x$ 实际上非常大，也就说这条路是走不通的。

那么我们换一条路，毕竟随机交换这个条件还没有用到。

设随机变量 $R:\Omega_y \to \mathrm{pair}$ 表示一次随机操作修改了 $r=(u,v)$ ，则

$\mathrm{E}_i(X \mid Y=y) = \sum_r\mathrm{Pr}_i(R=r\mid Y=y)\cdot \mathrm{E}_i[(X \mid Y=y) \mid(R=r)]$

根据条件概率的性质

$\mathrm{Pr}_i(R=r \mid Y=y)=\frac{\mathrm{Pr}_i(R=r,\,Y=y)}{\mathrm{Pr}_i(Y=y)}$

这个 $\mathrm{Pr}_i(R=r,\,Y=y)$ 相当于做完操作 $r$ 后，$i$ 随机加 $k(k=-1,\,0,\,1)$ 后的 $\mathrm{Pr}_i(Y=y)$ 。

显然这是相互独立的两部分，即 $R=r$ 和 $((Y=y) \mid i)$ 。这从直观上确实很显然。

不妨记 $i$ 随机加 $k$ 后的值为 $\mathtt{next}(i,r)$ ，符号语言就是

$\mathrm{Pr}_i(R=r,\,Y=y) = \mathrm{Pr}(R=r)\cdot\mathrm{Pr}_{\mathtt{next}(i,r)}(Y=y)$

那么

$\mathrm{E}_i(X \mid Y=y) = 1 + \sum_r\frac{\mathrm{Pr}_{\mathtt{next}(i,r)}(Y=y) \cdot \mathrm{Pr}(R=r)}{\mathrm{Pr}_i(Y=y)}\cdot \mathrm{E}_{\mathtt{next}(i,r)}(X \mid Y=y)$

令 $g_i = \mathrm{E}_i(X \mid Y=y)$ ，即设 $g_i$ 为字符 $y$ 的个数有 $i$ 个时 $s$ 变成 $y$ 的期望，则

$g_i = 1 + g_{i-1}\left(\frac{i(n-i)}{n(n-1)}\cdot \frac{i-1}{i}\right) + g_{i+1}\left(\frac{i(n-i)}{n(n-1)}\cdot \frac{i+1}{i}\right) + g_{i}\left(1-\frac{2 i(n-i)}{n(n-1)}\right)$

这一步看上去有点跳跃，其实是考察每个 $g_{i-1},\,g_i,\,g_{i+1}$ 分别的概率。列 dp 式子的过程而已。

那么

$g_i=\frac{n(n-1)}{2 i(n-i)}+\frac{i-1}{2 i} g_{i-1}+\frac{i+1}{2 i} g_{i+1}$

记 $c_l$ 为字符 $s_l$ 的出现次数，答案就是

$\frac{1}{n}\sum_{l=1}^n c_l\cdot g_{c_l}$

那么这个 $g_i$ 怎么求呢？参考高斯消元的线性技巧（注意到本题 $g_n=0$ ）

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))

char s[N];
int n, tot[N]; double inv, p, ans, f[N], a[N], b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); n = strlen(s + 1);
    if(n == 1) return cout << "0.0\n", 0; 
    for(int i = 1; i <= n; i++) tot[s[i] - 'A']++;
    a[1] = -1; b[1] = 0.5 * n;
    for(int i = 2; i < n; i++)
    {
        inv = 0.5 / i; p = 1 - (1 - i) * inv * a[i - 1];
        a[i] = (-1 - i) * inv / p;
        b[i] = (n * (n - 1) * inv / (n - i) - (1 - i) * inv * b[i - 1]) / p;
    }
    for(int i = n - 1; i; i--) f[i] = b[i] - a[i] * f[i + 1];
    for(int i = 0; i < 26; i++) ans += (double)tot[i] / n * f[tot[i]];
    cout << fixed << setprecision(1) << ans << '\n';
    return 0;
}