题解 P5516 【[MtOI2019]小铃的烦恼】
Scarlet_Hypoc
·
·
题解
建议进博客看，不然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
显然的，因为 $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}
$$
别忘了常数也要除。
于是就可以看代码了（很短）：
```cpp
#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);
}
```