【概率论，期望，观察，高斯消元】P5516 [MtOI2019]小铃的烦恼

· · 题解

给定一个长度为 n 的字符串 s，每次操作选择两个不同的下标 a,b，将 s_a 变为 s_b，求使得整个 s 完全相同的期望操作次数。

我们考虑全期望公式，答案显然可以表示为

E(X)=\sum_y P(Y=y)E(X|Y=y)

我们先考虑如何求出 P(Y=y)，也就是最终整个串变为 y 的概率。

显然这个东西并不是处处相等的，我们考虑它和什么有关，暴力的想法是记录整个串每一位是否 =y 的 0/1 串。

容易发现事实上并不需要这么多状态，它只和当前串中 =y 的字符数有关。那么我们可以浅做一个 DP，记 f_i 为当前字符串中 =y 的字符有 i 个时最终整个串变为 y 的概率，那么有（事实上，在状态确定后的这部分推导本质上属于全概率公式）

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

整理得

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

显然有 f_0=0,f_n=1，我们从 n 较小的情况开始归纳可以得到 f_i=\frac{i}{n}，即 P_i(Y=y) = \frac{i}{n}。

现在我们的问题就是求出 E(X|Y=y)。

我们还是考虑记录 \sum [s_i=y] 做一个 DP，然而这次要乘上的概率有所不同。

设 R 为刻画操作的随机变量，那么对于 f 的 DP 我们只需要乘上 P_i(R=r)，而这次我们需要乘上的是 P_i((R=r)|(Y=y))，那么由贝叶斯公式有

P_i((R=r)|(Y=y))=\frac{P_i((Y=y)|(R=r))P_i(R=r)}{P_i(Y=y)}

显然 P_i((Y=y)|(R=r)) 相当于做完 R=r 这个随机操作，i 随机 +1,-1 或不变后的 P_i(Y=y)。

设 g_i 为当前字符串中 =y 的字符有 i 个时最终整个串变为 y 的期望操作数，略去推导过程，同理有

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

这个看起来就不是很好归纳了，我们考虑直接对它跑一个高斯消元，但是这是 \mathcal O(n^3)，又注意到这是每行只有三个数的经典矩阵，可以线性消元。从初等代数的角度来考虑，相当于待定 f_{1} 后，可以表示出 f_{2 \sim n}，而此时再将 f_n=0 代进去就可以解出来了。

复杂度瓶颈在于输入，若不输入全 1 矩阵，则时空复杂度均为 \mathcal O(n)。待定 f_1 的递推的实现相当于扩域。

const int N=2e3+5;
char s[N];
int n,c[26];
struct rs{
    db x,y;
    rs operator*(const db&p)const{return rs{x*p,y*p};}
    rs operator-(const db&p)const{return rs{x,y-p};}
    rs operator-(const rs&p)const{return rs{x-p.x,y-p.y};}
}f[N];
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=1;i<=n;i++)c[s[i]-'A']++;
    f[1]=rs{1,0};
    for(int i=1;i<n;i++){
        db p=i,x=n;
        f[i+1]=f[i]*((p*2)/(p+1))-f[i-1]*((p-1)/(p+1))-x*(x-1)/(p+1)/(x-p);
    }
    db f1=(-f[n].y)/f[n].x,as=0;
    for(int i=0;i<26;i++)as+=((db)c[i]/n)*(f[c[i]].x*f1+f[c[i]].y);
    printf("%.1lf",as);
    return 0;
}