洛谷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;
}