poj 2096 Collecting Bugs （期望）

某个系统中有n个子系统和m个bug类型，该系统每天会出现一个bug （属于某个子系统和某个bug类型），bug的类型是等概率的，bug也是等概率地出现在每个子系统的。问所有子系统都出现bug且所有的bug类型都出现的期望天数。

Input

Input file contains two integer numbers, n and s (0 < n, s <= 1 000).

Output

Output the expectation of the Ivan's working days needed to call the program disgusting, accurate to 4 digits after the decimal point.

Sample Input

1 2

Sample Output

3.0000

我们用E(i,j)E(i,j)表示他找到了ii个bug和jj个子组件，离找到nn个bug和ss个子组件还需要的期望次数，这样要求的就是E(0,0)E(0,0)，而E(n,s)=0E(n,s)=0，对任意的E(i,j)E(i,j)。
1次查找4种情况：
1. 没发现任何新的bug和子组件
2. 发现一个新的bug
3. 发现一个新的子组件
4. 同时发现一个新的bug和子组件

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1005;
double dp[maxn][maxn];
int main()
{
    int n,s;
    cin>>n>>s;
    memset(dp,0,sizeof(dp));
    for(int i=n; i>=0; i--)
    {
        for(int j=s; j>=0; j--)
        {
            if(n==i&&s==j)
                continue;
            double tp=(1.0-(double)i*j/(n*s));
            dp[i][j]+=(double)(n-i)*j/(n*s)*dp[i+1][j];
            dp[i][j]+=(double)i*(s-j)/(n*s)*dp[i][j+1];
            dp[i][j]+=(double)(n-i)*(s-j)/(n*s)*dp[i+1][j+1];
            dp[i][j]+=1.0;
            dp[i][j]/=tp;
        }
    }
    printf("%.4f\n",dp[0][0]);


    return 0;
}