1 //http://www.cnblogs.com/yefeng1627/archive/2013/04/24/3040112.html 2 #include
      
        3 #include
       
        //最好开这个库//数学计算交c++更快 4 #include
        
          5 #include
         
           6 #include
          
            7 #define maxn 410000 8 double F[maxn]; 9 void builtF()10 {11     F[1]=0;12     for(int i=1;i<=maxn;i++)13     {14         F[i]=F[i-1]+log((double)i);15     }16     return ;17 }18 double getC(int n,int m)19 {20    // if (m==0) return 1;画蛇添足21     double ans=F[n]-F[n-m]-F[m];22     return ans;23 }24 using namespace std;25 int main()26 {27     builtF();28     int n;29     double p;30     int cas=0;31     while(~scanf("%d%lf",&n,&p))32     {33         cas++;34         double p1=log(p);35         double p2=log(1-p);36         double ans=0;37         for(int i=0;i<=n-1;i++)38         {39             ans+=(n-i)*((exp(+getC(n+i,i)+(n+1)*p1+i*p2)+exp(+getC(n+i,i)+(n+1)*p2+i*p1)));40         }41         printf("Case %d: %.6f\n",cas,ans);42     }43     return 0;44 }
          
         
        
       
      

问题描述：两个盒子，各装n个球，每次打开一个盒子，并拿走一个球，已知每次打开盒子1的概率是p，直到某次打开一个盒子是空的，求另一个盒子剩余的球数的期望。

关键算法：1、概率计算时有个坑，就是空盒子被打开了n+1次，而不是n次。

                  所以答案就是=sum{(n-i)*C(i,n+i)*p^n*(1-p)^i*p} + sum{(n-i)*C(i,n+i)*(1-p)^n*p^i*(1-p)}   0<=i<n, i 表示非空盒中已拿走的球的个数

              2、对数放缩：

              （1）C(m,n)=n!/(m!*(n-m)!) ==>  log(C(m,n))=log(n!)-log(m!)-log((n-m)!) 要知道log（10000！）都是很小的，解决了组合数存储爆long long的问题；

              （2）我们知道p是小于1的小数，那么在p^n,n很大时就会损失精度，double也不可存储，所以我们用 log（p^n）=nlog(p);自然就可存储下来了

              （3）还原时，使用exp（sum）即可，但是要注意，使用cmath库中的数学函数时，用c++提交会大大减少时间，是900ms到200ms的差距啊！！！！