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;
}