首页 > 代码库 > UVa 1639 (期望) Candy

UVa 1639 (期望) Candy

题意:

两个盒子里各有n颗糖,每天有p的概率从第一个盒子里取一颗糖,1-p的概率从第二个盒子里去一颗糖。直到某一天打开某个盒子忽然发现没糖了,求另一个盒子里剩余糖果数的期望。

分析:

紫书上面已经分析的很清楚了,而且也给出了解决精度损失问题的方法,就是先取对数然后再乘幂。

技术分享
 1 #include <cstdio> 2 #include <cmath> 3  4 const int maxn = 200000 + 5; 5 long double logF[maxn * 2 + 1]; 6  7 long double logC(int n, int m) 8 { 9     return logF[n] - logF[m] - logF[n-m];10 }11 12 int main()13 {14     //freopen("in.txt", "r", stdin);15     for(int i = 1; i <= maxn*2; ++i)16         logF[i] = logF[i-1] + log(i);17 18     int n, kase = 0;19     double p;20     while(scanf("%d%lf", &n, &p) == 2)21     {22         double ans = 0.0;23         for(int i = 1; i <= n; ++i)24         {25             long double c = logC(2*n-i, n);26             long double v1 = c + (n+1)*log(p) + (n-i)*log(1-p);27             long double v2 = c + (n+1)*log(1-p) + (n-i)*log(p);28             ans += i * (exp(v1) + exp(v2));29         }30         printf("Case %d: %.6f\n", ++kase, ans);31     }32 33     return 0;34 }
代码君

 

UVa 1639 (期望) Candy