彩球 概率期望

题目描述

　　袋子里有n个球。每次依次取出两个，把第二个球涂成第一个球的颜色，然后放回袋里搅匀。你的任务是算出在平均情况下，让所有球的颜色相同所需要的取多少次球（即：次数的数学期望）。

题目大意

　　略A.A

数据范围

　　字符串长度小于25

样例输入

ball.in AB ball.in ZCZ ball.in KLM ball.in AAABB

样例输出

ball.out 1.000000 ball.out 3.000000 ball.out 4.000000 ball.out 11.666667

解题思路

设f[i][j][k]为操作k次，第i种颜色有j个的概率 f[i][j+1][p+1]+=f[i][j][p]×(j/len)×((len-j)/(len-1)); f[i][j-1][p+1]+=f[i][j][p]×(len-j/len)×(j/(len-1)); f[i][j][p+1]+=f[i][j][p]×(j/len)×((j-1)/(len-1)); f[i][j][p+1]+=f[i][j][p]×((len-j)/len)×((len-j-1)/(len-1)); 答案=∑∞step=0f[i][len][step]$/sum_{step=0}^∞f[i][len][step]$

代码