自动搬运

查看原文

来自洛谷，原作者为

	Scarlet_Hypoc ...

搬运于2025-08-24 22:11:35，当前版本为作者最后更新于2020-04-14 16:07:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

建议进博客看，不然LaTeX可能会炸qwq。

顺便安利一下蒟蒻的CSDN博客。

根据 $\sum_{i=1}^n\sum_{j=1}^ns_{i,j}=n^2$ 这个约束，显然每个 $s_{i,j}$ 恒定为 $1$，也就是每次操作总会成功，所以可以忽略成功概率这个东西。

最后全部元素会相同，但是不知道是什么元素，所以我们需要枚举最后的元素（下面称为目标元素）是谁。

然后又发现，一种元素最后成为目标元素的概率，取决于一开始序列中有多少个这种元素，而每次操作，有概率使目标元素增加或减少 $1$，也可能不变，于是得到 $dp$ 方程：设 $p[i]$ 表示此时有 $i$ 个目标元素，使全部元素都变成目标元素的概率是多少。

那么有：

$$\begin{aligned} p[i]=\frac {i(n-i)} {n(n-1)} p[i-1]+\frac {i(n-i)} {n(n-1)}p[i+1]+(1-2\frac {i(n-i)} {n(n-i)})p[i] \end{aligned} $$

意思是，有 $\frac {i(n-i)} {n(n-1)}$ 的概率目标元素 $-1$，也有 $\frac {i(n-i)} {n(n-1)}$ 的概率 $+1$，剩下的概率就是不变，这个概率应该很好理解。

整理一下就是 $p[i]=\frac {p[i-1]+p[i+1]} 2$。

$\because p[i+1]-p[i]=p[i+1]-\frac {p[i+1]+p[i-1]} 2=\frac {p[i+1]-p[i-1]} 2$ 且 $p[i]-p[i-1]=\frac {p[i+1]+p[i-1]} 2-p[i-1]=\frac {p[i+1]-p[i-1]} 2$ $\therefore p[i+1]-p[i]=p[i]-p[i-1]$ ，即 $p$ 是个等差数列

显然的，因为 $p[0]=0$（没有目标元素，不可能使全部元素变成目标元素），以及 $p[n]=1$（已经满足全部都是目标元素了），所以得到 $p[i]=\frac i n$。

为了方便，下面称能使所有元素变为目标元素为有解。

求出概率之后，在这基础上，考虑期望步数，因为如果无解的话，步数就无从谈起了。

设 $f[i]$ 表示有 $i$ 个目标元素，使全部元素变成目标元素的期望步数。

方程类似上面 $p[i]$ 的方程，但是只考虑目标元素变化的情况。可以发现，目标元素变化（$+1$ 或 $-1$）的概率为 $\frac {2i(n-i)} {n(n-1)}$，即操作 $1$ 次，期望变化 $\frac {2i(n-i)} {n(n-1)}$，我们要使得变化为 $1$，就要操作它的倒数 $\frac {n(n-1)} {2i(n-i)}$ 次，也就是满足操作次数*单次操作变化量=总变化量。

于是可以得到方程：

$$p[i]f[i]=p[i]\times \frac {n(n-1)} {2i(n-i)}+\frac 1 2 p[i-1]f[i-1]+\frac 1 2 p[i+1]f[i+1] $$

前面的 $\frac {n(n-1)} {2i(n-i)}$ 也就是操作次数，操作完后，参照上面 $p$ 的方程，可以发现目标元素数量 $-1$ 和 $+1$ 的概率相同，所以这里有一半几率转移到 $f[i-1]$，有一半几率转移到 $f[i+1]$。

以及上面的 $f[i]$ 前面乘了 $p[i]$，因为只有 $p[i]$ 的概率存在 $f[i]$（即有解），另外有 $1-p[i]$ 的概率无解，所以 $f[i]$ 能做出的期望贡献其实只有 $p[i]\times f[i]$。

以及在操作次数前乘的 $p[i]$ 也是类似的：只有 $p[i]$ 的概率往有解的方向转移。既然是往有解的方向转移了，那么后面的 $f[i-1]$ 和 $f[i+1]$ 自然也要乘上 $p[i-1]$ 和 $p[i+1]$。

由于 $p[i]$ 我们是知道的，所以整理一下这个柿子就变成了：

$$\begin{aligned} f[i]&=\frac {n(n-1)} {2i(n-i)}+\frac {i-1} {2i}f[i-1]+\frac {i+1} {2i}f[i+1]\\ f[i]-\frac {i-1} {2i}f[i-1]-\frac {i+1} {2i}f[i+1]&=\frac {n(n-1)} {2i(n-i)} \end{aligned} $$

边界的话显然有 $f[n]=0$，这样我们就得到了 $n-1$ 个方程，用高斯消元解一波就得到 $f$ 了。

什么？你说 $O(n^3)$ 过不了？不不不，这题我们需要用有技巧的高斯消元，只用 $O(n)$。

观察上式发现，第 $i$ 个方程只有第 $i-1,i,i+1$ 三项有系数，以及当 $i=1$ 时，$f[0]$ 的系数是 $0$，也就是大概长这样（$x$ 表示系数不为 $0$）：

$$\begin{matrix} & 0 & 1 & 2 & 3 & 4 & 5\\ 1 & 0 & 1 & x_1 & 0 & 0 & 0\\ 2 & 0 & x_2 & 1 & x_3 & 0 & 0\\ 3 & 0 & 0 & x & 1 & x & 0\\ 4 & 0 & 0 & 0 & x & 1 & x\\ \end{matrix} $$

消元的时候，可以发现，第 $i$ 行只需要消第 $i+1$ 行就够了，并且只需要消第 $i$ 和第 $i+1$ 个元素即可，比如上面，第一行消第 $2$ 行得到：

$$\begin{matrix} & 0 & 1 & 2 & 3 & 4 & 5\\ 1 & 0 & 1 & x_1 & 0 & 0 & 0\\ 2 & 0 & 0 & 1-x_1x_2 & x_3 & 0 & 0\\ 3 & 0 & 0 & x & 1 & x & 0\\ 4 & 0 & 0 & 0 & x & 1 & x\\ \end{matrix} $$

这样看来，实现的时候每行只需要记录 $3$ 个变量（上面看到的两个系数以及后面没写出来的常数），但是学习官方题解，我们可以更贪一点，只记两个变量，方法就是第 $i$ 行消完第 $i+1$ 行时，让 $i+1$ 行的方程全部除以第 $i+1$ 个元素，这样第 $i+1$ 个元素就是 $1$，就没必要存了，上面的例子弄一下就是：

$$\begin{matrix} & 0 & 1 & 2 & 3 & 4 & 5\\ 1 & 0 & 1 & x_1 & 0 & 0 & 0\\ 2 & 0 & 0 & 1 & \frac {x_3} {1-x_1x_2} & 0 & 0\\ 3 & 0 & 0 & x & 1 & x & 0\\ 4 & 0 & 0 & 0 & x & 1 & x\\ \end{matrix} $$

别忘了常数也要除。

于是就可以看代码了（很短）：

#include <cstdio>
#include <cstring>
#define maxn 2010

int n,tot[maxn];
char s[maxn];
double f[maxn],a[maxn],b[maxn],inv,p,ans=0.0;

int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	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];
		//p就是上面说的"第i+1个元素"，由于这里是让第i-1行消第i行，所以这里应该说是第i个元素
		a[i]=(-1-i)*inv/p;//真正的第i+1个元素
		b[i]=(n*(n-1)*inv/(n-i)-(1-i)*inv*b[i-1])/p;//常数
	}
	for(int i=n-1;i>=1;i--)f[i]=b[i]-a[i]*f[i+1];
	for(int i=0;i<26;i++)ans+=1.0*tot[i]/n*f[tot[i]];
	printf("%.1lf",ans);
}