巧克力（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 ;

}

巴特西

巧克力（zoj 1363）

最新文章

热门文章