POJ 1322 Chocolate

Description

Input

Output

Sample Input

5 100 2

0

Sample Output

0.625 

Source

题意：C种颜色的巧克力在桶中，从里面依次拿出n个巧克力，颜色同样的吃掉，求最后剩下m个巧克力的概率

当n>1000 时候，考虑奇偶性取1000或1001就可以，由于非常大的时候概率会趋于稳定，至于奇数时取1001 偶数

时取1000有些不解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#define N 1010
using namespace std;
double dp[N][110];
int main()
{
    int c,n,m;
    while(scanf("%d",&c)!=EOF)
    {
        if(c==0)
        {
            break;
        }
        scanf("%d %d",&n,&m);
        if(m>c||m>n||(n-m)%2)
        {
            printf("0.000\n");
            continue;
        }
        if(n>1000)
        {
            n = 1000+n%2;
        }
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        dp[1][1] = 1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=i&&j<=c;j++)
            {
                if(j-1>=0)
                {
                    dp[i][j] = dp[i-1][j-1]*(double)(c-j+1)/(double)c;
                }
                dp[i][j] += dp[i-1][j+1]*(double)(j+1)/(double)c;
            }
        }
        printf("%.3lf\n",dp[n][m]);
    }
    return 0;
}