HDU 4465 - Candy(概率与数学优化)
2012成都Regional的B题,花了一个小时推出了式子,但是搞了好久发现都控制不了精度,后来突然想到组合数可以用log优化,改了之后就AC了比较水的概率题
#include <stdio.h> #include <math.h> #define maxn 200005 double f[2*maxn]; double c(int a,int b) { return f[a]-f[a-b]-f[b]; } int main() { f[0]=0; for(int i=1;i<2*maxn;i++) { f[i]=f[i-1]+log(1.0*i); } double ans; double p; int n,cas=0; while(scanf("%d%lf",&n,&p)==2) { ans=0; double u=log(p),v=log(1-p); for(int i=1;i<=n;i++) { double k1=c(2*n-i,n-i)+(n-i)*u+(n+1)*v; double k2=c(2*n-i,n-i)+(n-i)*v+(n+1)*u; ans+=i*(exp(k1)+exp(k2)); } printf("Case %d: %lf\n",++cas,ans); } return 0; }
补充:软件开发 , C++ ,