UVA - 1639 -Candy

题目链接：https://vjudge.net/problem/UVA-1639

题目大意：

有两个糖果盒，每个盒子里面有n个糖果，每天随机选一个（概率分别为p,1-p），然后吃一颗糖。直到有一天，打开盒子一看，没有糖了。

输入n,p;求此时另外一个盒子里面糖的个数的数学期望。

题目分析：

可以假设另外一个盒子里面还剩下i个，此时一共选了n+n-i次，所以共有C(2n-i,n)种组合，期望为i*C(2n-i,n)*p^(n+1)*(1-p)^(n-i)+i*C(2n-i,n)*(1-p)^(n+1)*(p)^(n-i);

注意这里面组合数可能非常大，而后面的概率会很小，此时会损失很大的精度。这里可以使用取Log的方法，将乘法转换成减法，然后取e的指数次方即可。

另外可以预先打表求出组合数取log的值降低复杂度。

给出代码：

 #include <cstdio>
 #include <iostream>
 #include <string>
 #include <cmath>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 typedef long double ld;
 *1e5+;
 ];
 ld logc(int n,int m)
 {
    return logF[n]-logF[m]-logF[n-m];
 }
 int main()
 {
     ;i<=;i++)
          logF[i]=logF[i-]+log(i);
      ;double p;
      while(cin>>n>>p)
      {
          ;
          ;i<=n;i++)
          {
             ld c=logc(*n-i,n);
             ld v1=c+(n+)*log(p)+(n-i)*log(-p);
             ld v2=c+(n+)*log(-p)+(n-i)*log(p);
             ans+=i*(exp(v1)+exp(v2));
          }
          printf("Case %d: %f\n",cas++,ans);
      }
      ;
 }

巴特西

UVA - 1639 -Candy

最新文章

热门文章