这道题是真的考验得分技巧
如果n<=5,那么直接用随机数模拟
n大一点的时候呢？
我们分开单独考虑每一个颜色
考虑一个颜色时，可以把这个颜色看成白球，其他颜色看成黑球，我们要求的就是全部变成白球的期望步数，此时我们设(f[i])为当前有i个白球，全部变成白球的期望步数
而且我们每次操作不一定会出现黑变白或白变黑的情况，发生这种情况的概率是(frac{2i(n-i)}{n(n-1)})(假设当前有i个白球)，就相当于进行(frac{n(n-1)}{2i(n-i)})次操作才能发生颜色改变。
我们就能写下(f[i]=frac{n(n-1)}{2i(n-i)} + frac{1}{2} f[i+1]+frac{1}{2}f[i-1])
但这是错的。
因为我们发现有的时候会出现全部变成黑球的情况，所以这是个条件概率。
设目前有i个白球，最后能全变成白球的概率是(g[i]),显然(g[0]=0),(g[n]=1),(g[i]=frac{g[i-1]+g[i+1]}{2})
显然(g)数组就是个等差数列，(g[i]=frac{i}{n})
按照比例把概率中的1分给(f[i-1])和(f[i+1])
我们就能写下(f[i]=frac{n(n-1)}{2i(n-i)} + frac{i-1}{2i}f[i-1] + frac{i+1}{2i} f[i+1])
这就是对的了。
我们可以用高斯消元处理,时间复杂度为(O(n^3))
但这题n<=10000
这时候就要用到线性高斯消元的技巧了
设(f[i]=k[i]f[i+1]+b[i])
考虑利用这个式子将上面方程进行消元，将这个式子中带入方程右边的第二项，得到
$f[i]=frac {n(n-1)}{2i(n-i)}+frac {i-1}{2i}k[i-1]f[i]+frac {i-1}{2i}b[i-1]+frac {i+1}{2i}f[i+1] $
$ (1-frac {i-1}{2i}k[i-1])f[i]=frac {i+1}{2i}f[i+1]+frac {i-1}{2i}b[i-1]+frac {n(n-1)}{2i(n-i)} $
$ f[i]=frac {frac {i+1}{2i}}{1-frac {i-1}{2i}k[i-1]}f[i+1]+frac {frac {i-1}{2i}}{1-frac {i-1}{2i}k[i-1]}b[i-1]+frac {frac {n(n-1)}{2i(n-i)}}{1-frac {i-1}{2i}k[i-1]} $
和(f[i]=k[i]f[i+1]+b[i])相比，可得
$ k[i] = frac{frac{i+1}{2i}}{1-frac{i-1}{2i}k[i-1]} $
$ b[i] = frac {frac {i-1}{2i}b[i-1]+frac {n(n-1)}{2i(n-i)}}{1-frac {i-1}{2i}k[i-1]} $
然后由于(f[0])没有意义，就无需从此转移，所以得到特殊情况
(f[1]=frac {n(n-1)}{2 imes 1cdot (n-1)}+f_2=frac n2+f[2])
又由于(f[1]=k[1]f[2]+b[1])，可以得到在(i=1)下的特殊情况:
(k[1]=1)
(b[1]=frac {n}{2})
然后求出(f[i])就能求出答案了。
代码极短
#include<iostream>
#include<cstring>
#include<cstdio>
#define DB double
using namespace std;
int n;
DB ans;
const int N=10010;
int tong[30];
DB k[N],b[N],f[N];
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];
k[1] = 1; b[1] = 0.5 * n;
for(int i = 2;i <= n - 1;++ i)
{
DB tmp1,tmp2;
tmp1 = 0.5 / i;
tmp2 = 1.0 / (1 - (i - 1) * tmp1 * k[i - 1]);
k[i] = (DB)(i + 1) * tmp1 * tmp2;
b[i] = ((i - 1) * tmp1 * b[i - 1] + n * (n - 1) * tmp1 / (n - i)) * tmp2;
}
for(int i = n - 1;i >= 1;-- i)f[i] = f[i+1] * k[i] + b[i];
for(int i = 1;i <= 26;++ i)ans += (DB)tong[i] / n * f[tong[i]];
printf("%0.1f",ans);
return 0;
}