学步园

      题意：两个瓶子里都装了n个糖果；从第一个瓶子拿的概率是p  ， 当你再拿糖果的时候，发现瓶子空了 ，求这时候另外一个瓶子的剩余的糖果的数量的期望   (1 ≤ n ≤ 2 × 10^5)

这题的概率DP公式好求，即

但c（n,m） 太大，会上溢出， p^k 太小，会下溢出，这时就要用到 log  求组合了

对于问题一:

　　排列过大,考虑到 y = logx 函数, log(n!) 也不会很大. 又

　　令 f(x) = log( x! ),则有 

　　预处理出 函数f() 就可以 O(1)求出 log( \binom{n}{m} )了. 然后 再求个 exp( x ) 就可以还原了.

        exp(x )    返回以 e 为底数、以给定数字为指数的幂。

对于问题二:

　　p^x 值过小. log( p^x ) = x * log p 这样值就在可控范围内. 同样一次 exp( x ) 就可以还原

代码如下：

#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

#define N 400005
double f[N];

double C(int n,int m)
{
    return f[n]-f[m]-f[n-m]; //c(n,m)=n!/((n-m)!*m!)  log(c(n,m))=log(n!)-log(m!)-log((m-n)!)  
}

int main()
{
    int i,n,j,t=0;

    f[0]=0;
    for(i=1;i<N;i++)
      f[i]=f[i-1]+log(i*1.0);

    double p,q,res;
    while(~scanf("%d%lf",&n,&p))
    {
        t++;
        q=1.0-p;
        res=0;
        for(i=0;i<n;i++)
        {
           res=res+1.0*(n-i)*(exp( C(n+i,i)+i*log(p)+(n+1)*log(q))+exp(C(n+i,i)+i*log(q)+(n+1)*log(p)));
        }
        printf("Case %d: %.6lf\n",t,res);
    }
    return 0;
}

还有一种方法是直接求的，没用log

是边求组合数一边求概率

#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int i,n,j,t=0;
    double p,q,res,ca,cb;
    while(~scanf("%d%lf",&n,&p))
    {
        t++;
        q=1.0-p;
        ca=cb=1.0;
        int exp=n+1;
        res=n*(pow(q,exp)+pow(p,exp));
        for(i=1; i<n; i++)
        {
            ca=ca*(n+i)*p/i;
            cb=cb*(n+i)*q/i;
            while(ca>n||cb>n)
            {
                ca=ca*q;
                cb=cb*p;
                exp--;
            }
            res+=ca*(n-i)*pow(q,exp);
            res+=cb*(n-i)*pow(p,exp);
        }
        printf("Case %d: %.6lf\n",t,res);

    }
    return 0;
}