UVA - 1639 Candy——期望+log处理精度

根据题意，不妨设最后打开第一个盒子，此时第二个盒子还有i颗糖果，因此这之前一共打开了n+(n-i)次盒子，其中n次取盒子1，n-i次取盒子2，取法一共有C(2*n-i,n)种，因此盒子2还剩i颗糖果时的概率是C(2*n-i,n)*p^(n+1)*(1-p)^(n-i)。注意最后一次打开盒子1的概率也要算上。有了概率，根据期望的定义不难求出答案。但需要注意的是，由于n可能非常大，因此要利用对数来计算，防止过多的精度损失。为了提高程序效率，可以事先算好n!取自然对数的值，便于后续计算

最后注意要用long double处理精度

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
typedef long double ld;
const int maxn = 2 * 1e5 + 10;
ld Log[2 * maxn];
int main() {
    int n, kase = 1;
    double p;
    Log[0] = 0.0;
    for (int i = 1; i < 2 * maxn; i++) Log[i] = Log[i - 1] + log(1.0 * i);
    while (scanf("%d %lf", &n, &p) == 2) {
        double ans = 0.0;
        for (int i = 1; i <= n; i++) {
            ld C = Log[2 * n - i] - Log[n] - Log[n - i];
            ld temp1 = C + log(p) * (n + 1) + log(1 - p) * (n - i);
            ld temp2 = C + log(1 - p) * (n + 1) + log(p) * (n - i);
            ans += (double)i * (exp(temp1) + exp(temp2));
        }
        printf("Case %d: %.6lf\n", kase++, ans);
    }
    return 0;
}