Collecting Bugs 题解

根据上课听的雨巨的思路，移项运算一下然后写代码

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