题目传送门

简要题面:

一个程序有n个子程序。有s种bug,每天能等概率随机在一个子程序中找到一个bug,如果一个子程序中的一种bug被找到了,再下一次这个子程序的这种bug被找到的概率依然不变。问期望至少需要多少天能在每个子程序中都至少找到一个bug,把每一种bug都最少找到一次。

简要题解

设$f[i][j]$表示已经在i个程序中找到bug,找到j种bug,离任务完成期望还需要的天数。
显然$f[n][s]=0$,我们要求$f[0][0]$。
$$f[x][y]=\frac{xy}{ns}f[x][y]+\frac{(n-x)y}{ns}f[x+1][y]+\frac{x(s-y)}{ns}f[x][y+1]+\frac{(n-x)(s-y)}{ns}f[x+1][y+1]+1$$
右边的$f[x][y]$减到左边得
$$\frac{ns-xy}{ns}f[x][y]=\frac{(n-x)y}{ns}f[x+1][y]+\frac{x(s-y)}{ns}f[x][y+1]+\frac{(n-x)(s-y)}{ns}f[x+1][y+1]+1$$
把左边fx的系数除到右边得

$$ \begin{align} f[x][y] & = \frac{ns}{ns-xy}(\frac{(n-x)y}{ns}f[x+1][y]+\frac{x(s-y)}{ns}f[x][y+1]+\frac{(n-x)(s-y)}{ns}f[x+1][y+1]+1) \\\\ & = \frac{ns}{ns-xy} \frac{(n-x)y f[x+1][y]+x(s-y)f[x][y+1]+(n-x)(s-y)f[x+1][y+1]+ns}{ns} \\\\ & = \frac{(n-x)y f[x+1][y]+x(s-y)f[x][y+1]+(n-x)(s-y)f[x+1][y+1]+ns}{ns-xy} \end{align} $$

结束。

标签: 概率期望, DP

添加新评论