hdu 4465 Candy (概率期望）

分析：

1、直接推出公式为：(n-k)*sigma(C(n+k，k)*p^k*(1-p)^(n+1)+C(n+k,k)*(1-p)^k*p^(n+1))

2、公式中幂的计算可能出现很大的数。可以先缩小后放大（先取对数再指数还原），也可以

通过循环控制精度。

3、要把重复用到的数先计算出来，避免重复计算tle。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

double logm[400010];

double logC(int m,int n)
{
    return logm[m]-logm[n]-logm[m-n];  //C(m,n)=m!/(n!*(m-n)!)取对数变成加减法运算
}

int main()
{
    double p,q,ans,tmp,lq,lp;
    int n,cas=1,i;
    logm[0]=log(1.0);
    logm[1]=log(1.0);
    for(i=2;i<=400000;++i)
    {
        logm[i]=logm[i-1]+log(1.0*i); //log(n!)=log((n-1)!)+log(n)
    }
    while(scanf("%d%lf",&n,&p)!=EOF)
    {
        lp=log(p),lq=log(1-p);
        ans=0;
        for(int k=0;k<=n;k++)
        {
            tmp=logC(n+k,k);
            ans+=(n-k)*(exp(tmp+(n+1)*lp+k*lq)+exp(tmp+(n+1)*lq+k*lp));
        }
        printf("Case %d: %.6lf\n",cas++,ans);
    }
    return 0;
}

循环控制的代码直接帖别人的

原创为：http://blog.csdn.net/qq172108805/article/details/9004655

/*
期望公式Ε=∑ P * N    p为概率 n为数量
 P=p*C(n,m)*pn*(1-p)m-n
 c(m,n)=c(m-1,n)*m/(m-n)
        概率
m=0      p^(n+1)
m=1      p^(n+1)q
m=2      p^(n+1)q^2

q的幂通过循环何以控制
p的还需要补充
 
*/
#include<math.h>
#include<stdio.h>
double pro(int n,double p)
{
    double zhong=1,ret=n*p;
    for(int m=1;m<=n;++m)//从第二个瓶子取m个
    {
        zhong*=p*(1-p)*(m+n)/m;
        ret+=(n-m)*zhong;
        ret*=p;
    }
    return ret;
}
int main()
{
    int n,index=1;
    double p;
    while(~scanf("%d%lf",&n,&p))
    {
        double ret=pro(n,p)+pro(n,1-p);
        printf("Case %d: %.6lf\n",index++,ret);
    }
    return 0;
}

hdu 4465 Candy (概率期望）

原文：http://blog.csdn.net/u012841845/article/details/18861925