期望DP
枚举最终能成为哪个颜色，把这个颜色看做白球，其余颜色看成黑球。最后分别把每种颜色的期望加起来就行。
考虑当前有i个白球，全变成白球期望步数设为f[i]
一次操作可能造成有白球变黑或者黑球变白的概率：\(\frac{i(n-i)}{C^2_n}\)，也就是期望\(\frac{C^2_n}{i(n-i)}\)次操作会造成有白球变黑或者黑球变白。
很容易写错成
\(f[i]=\frac{C^2_n}{i(n-i)}+\frac{1}{2}∗f[i−1]+\frac{1}{2}∗f[i+1]\)
为什么是错的？你考虑一下f[1],能从f[0]转移来吗？不行的，f[0]没意义。
所以我们重新考虑f，f[i]应该是当前有i个白球，在能全变成白球条件下，全变成白球期望步数
设当前有i个白球，最终能全变成白球的概率是什么？设为g[i],每次操作等概率减少或增加白球，可知\(g[i]=\frac{1}{2}g[i-1]+\frac{1}{2}g[i+1]\)
且有\(g[0]=0\) 和 \(g[1]=1\)可知是等差数列，\(g[i]=\frac{i}{n}\)
那么f[i]按照g[i-1]和g[i+1]的比例来确定f[i-1]和f[i+1]前的系数，并且要注意这俩系数和为1
可得\(f[i]=\frac{C^2_n}{i(n-i)}+\frac{(i−1)}{2i}∗f[i−1]+\frac{i+1}{2i}∗f[i+1]\)
这个方程很特殊，可以O(n)消元解方程
#include<iostream>
#include<cstring>
#include<cstdio>
#define DB double
using namespace std;
int n;
DB ans;
const int N=10010;
int tong[30];
DB f[N],c[N][5];
char s[N];
int main()
{
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;++i)++tong[s[i]-'A'+1];
for(int i=1;i<=n;++i)
{
if(i!=1&&i!=n)c[i][1]=-1.0*(i-1)/(2*i);
c[i][2]=1;
if(i!=n)c[i][3]=-1.0*(i+1)/(2*i);
if(i!=n)c[i][4]=((1.0*n*n-n)/2.0)/(1.0*i*(n-i));
}
for(int i=2;i<=n;++i)
{
double bei=c[i][1]/c[i-1][2];
c[i][1]=0;c[i][2]-=c[i-1][3]*bei;
c[i][4]-=c[i-1][4]*bei;
}
for(int i=n-1;i>=1;--i)
{
double bei=c[i][3]/c[i+1][2];
c[i][3]=0;
c[i][4]-=c[i+1][4]*bei;
}
for(int i=1;i<=n;++i)c[i][4]/=c[i][2];
for(int i=1;i<=26;++i)ans+=(DB)tong[i]/n*c[tong[i]][4];
printf("%0.1f",ans);
return 0;
}