巧克力(zoj 1363)

时间:2023-03-10 01:55:15
巧克力(zoj 1363)

2100年,ACM牌巧克力将风靡全球。

“绿的,橘红的,棕色的,红的…”,彩色的糖衣可能是ACM巧克力最吸引人的地方。你一共见过多少种颜色?现在,据说ACM公司从一个24种颜色的调色板中选择颜色来装饰他们的美味巧克力。

有一天,Sandy用一大包有五种颜色的巧克力玩了一个游戏。每次他从包里拿出一粒巧克力并把它放在桌上。如果有桌上有两粒相同颜色的巧克力,他就把他们吃掉。他惊奇的发现大多数时候桌上都有2到3粒巧克力。

如果ACM巧克力有C(1≤C≤100)种颜色,在拿出了N(1≤N≤1000000)粒巧克力之后在桌上恰有M(1≤M≤1000000)粒的概率是多少?

/*
转移方程很好想,f[i][j]表示取了i个恰好有j个在桌子上的概率
f[i][j]=f[i-1][j+1]*(j+1)/c+f[i-1][j-1]*(j+1)/c
但是这道题的n特别大,所以考虑一种神奇的方法。
由于本题对精度的要求不高,而且越到后面,它与前面的相差并不大,所以我们可以只求一部分。
需要注意的是,当n+m是奇数时,概率一定是0,所以要奇偶划分。
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1010
using namespace std;
double dp[N][N];int c,n,m;
int main(){
freopen("jh.in","r",stdin);
while(scanf("%d",&c)&&c){
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&m);
if(!n&&!m){
printf("1.000\n");
continue;
}
if(m>c||m>n||(m+n&)){
printf("0.000\n");
continue;
}
if(n>){
if(n&) n=;
else n=;
}
dp[][]=;
for(int i=;i<=n;i++)
for(int j=;j<=min(i,c);j++){
if(i+j&) {dp[i][j]=;continue;}
if(j>) dp[i][j]+=dp[i-][j-]*double(c-j+)/double(c);
if(j+<i) dp[i][j]+=dp[i-][j+]*double(j+)/double(c);
}
printf("%.3lf\n",dp[n][m]);
}
return ;
}