有n个球排成一列，每个球都有一个颜色，用A-Z的大写字母来表示，我们每次随机选出两个球ball1,ball2,使得后者染上前者的颜色，求期望操作多少次，才能使得所有球的颜色都一样？输出保留一位小数。
题目分析：
liu_runda大佬的博客
把答案分成每种颜色，就是求最后合成某种颜色的概率*合成这种颜色的期望步数。
用g[i]g[i]g[i]表示这种颜色有iii个，最后nnn个全部变成这种颜色的概率。容易得到g[i]=12g[i−1]+12g[i+1]g[i]=\frac12g[i-1]+\frac12g[i+1]g[i]=21g[i−1]+21g[i+1]，边界g[0]=0,g[n]=1g[0]=0,g[n]=1g[0]=0,g[n]=1可以看出g[i]=ing[i]=\fracing[i]=ni
用f[i]f[i]f[i]表示这种颜色有iii个，最后nnn个全部变成这种颜色的期望步数。总共有n∗(n−1)n*(n-1)n∗(n−1)种方案，会使这种颜色数量改变的方案有2∗i∗(n−i)2*i*(n-i)2∗i∗(n−i)种，所以数量改变的概率P可求，期望1P\frac1PP1步后数量会改变。但是注意，我们是在最终全部都会变成这种颜色的条件下算的期望步数，所以我们的转移需要去掉那些不能到达这个条件的概率，iii转移到i−1i-1i−1和i+1i+1i+1的概率分别是12\frac1221，由i−1i-1i−1到达最终状态的概率是g[i−1]g[i-1]g[i−1]，所以f[i−1]f[i-1]f[i−1]对f[i]f[i]f[i]的贡献是12∗g[i−1]\frac12*g[i-1]21∗g[i−1]，而不是简单的12\frac1221。同理，f[i+1]f[i+1]f[i+1]的贡献是12∗g[i+1]\frac12*g[i+1]21∗g[i+1]。令G=12∗g[i−1]+12∗g[i+1]G=\frac12*g[i-1]+\frac12*g[i+1]G=21∗g[i−1]+21∗g[i+1]，就有：f[i]=1G(12∗g[i−1]∗f[i−1]+12∗g[i+1]∗f[i+1])+1Pf[i]=\frac1G\left(\frac12*g[i-1]*f[i-1]+\frac12*g[i+1]*f[i+1]\right)+\frac1Pf[i]=G1(21∗g[i−1]∗f[i−1]+21∗g[i+1]∗f[i+1])+P1化简一下就是f[i]=(i−1)/(2i)∗f[i−1]+(i+1)/(2i)∗f[i+1]+n∗(n−1)2∗i∗(n−i)f[i]=(i-1)/(2i)*f[i-1]+(i+1)/(2i)*f[i+1]+\frac{n*(n-1)}{2*i*(n-i)}f[i]=(i−1)/(2i)∗f[i−1]+(i+1)/(2i)∗f[i+1]+2∗i∗(n−i)n∗(n−1)f[0]f[0]f[0]无意义，f[n]=0f[n]=0f[n]=0，把f[i]f[i]f[i]代成a[i]∗f[1]+b[i]a[i]*f[1]+b[i]a[i]∗f[1]+b[i]的形式递推，算出f[n]=a[n]∗f[1]+b[n]f[n]=a[n]*f[1]+b[n]f[n]=a[n]∗f[1]+b[n]，解出f[1]f[1]f[1]即可。
Code：
#include<bits/stdc++.h>#definemaxn10005usingnamespacestd;intn,cnt[26];doublef1,a[maxn],b[maxn],ans;chars[maxn];intmain(){scanf("%s",s),n=strlen(s);for(inti=0;i<n;i++)cnt[s[i]-'A']++;a[1]=1,b[1]=0;for(inti=1;i<n;i++){a[i+1]=(a[i]-a[i-1]*(i-1)/(2*i))*(2*i)/(i+1);b[i+1]=(b[i]-b[i-1]*(i-1)/(2*i)-1.0*n*(n-1)/(2*i*(n-i)))*(2*i)/(i+1);}f1=-b[n]/a[n];for(inti=0;i<26;i++)ans+=1.0*cnt[i]/n*(a[cnt[i]]*f1+b[cnt[i]]);printf("%.1f\n",ans);}
