有n个球排成一列，每个球都有一个颜色，用A-Z的大写字母来表示，我们每次随机选出两个球ball1,ball2,使得后者染上前者的颜色，求期望操作多少次，才能使得所有球的颜色都一样？
有n个球排成一列，每个球都有一个颜色，用A-Z的大写字母来表示，我们每次随机选出两个球ball1,ball2,使得后者染上前者的颜色，求期望操作多少次，才能使得所有球的颜色都一样？
挺不错的题！
其实n可以开到1e7
%%lrd真心好题解
思想：
1.26个太多，2个好做。
2.转化成2个？钦定哪一个最后成为最终颜色！这个是白色，剩下都是黑色。
发现问题：
问题1：不一定什么时候都能染成
概率：i/n
问题2：不能之前的f[i]剩下i个白球到全部是同样的颜色。必须都是白色并且都是黑色也不一定都是同样颜色的。
所以f[i]有i个白球，染成都是白色的期望步数
问题3：f[0]怎么定义？正无穷？
其实是条件概率，也就是，对于所有情况（S种），我们把所有最终变成char这种字母的情况拿出来（K种），统计每一个方案的步数，乘上概率(1/K)
再乘上：K/S，这里就是cnt[char]/n
所以其实，f[i]有一个条件，只统计能到达想要的全白状态下的期望步数
所以转移只用考虑“占比”（也就是占x/K），显然(i+1)的概率高，(i-1)的概率低，所以占比就是i+1:i-1
然后转移方程就列出来了
原文：https://www.cnblogs.com/Miracevin/p/10516979.html