题解 UVA11427 【Expect the Expected】

void solve(int now) {   
    clr(dp, 0);
    scanf("%d/%d %d", &a, &b, &N);
    double p = (double) a / (double) b;
    dp[0][0] = 1;
    rep(i, 1, N) {
        dp[i][0] = dp[i - 1][0] * (1 - p);
        rep(j, 1, N) {
            dp[i][j] += dp[i - 1][j] * (1 - p);
            if(a * i >= b * j) 
                dp[i][j] += dp[i - 1][j - 1] * p;
        }
    }
    double Ans = 0;
    rep(i, 0, N)
        Ans += dp[N][i];
    printf("Case #%d: %d\n", now, (int) (1.0 / Ans));
}