POJ-1322 Chocolate 동적 계획

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

/*
  :                     ,             1/C
                   ,          ,         . 
       N  ,            M       
     
  :   dp[i][j]  i    j         ,           ,  
               dp ,   dp  :
     dp[i][j] = dp[i-1][j-1] * (C-j+1)/C + dp[i-1][j+1] * (j+1)/C
                          ,            
                    ,             
     
            , N  1000   ,      1000  ,         
     1001  ,  N    ,                    
*/

int C, M, N; 
double dp[2][1005][105]; 

void DP() {
    memset(dp, 0, sizeof (dp)); 
    dp[1][1][1] = 1.0; //                
    for (int i = 2; i <= N; ++i) {
        int x = i & 1;
        for (int j = 0; j <= C; ++j) {
            if (j - 1 >= 0)
                dp[x][i][j] += dp[!x][i-1][j-1]*(C-j+1)/C;
            if (j + 1 <= C)
                 dp[x][i][j] += dp[!x][i-1][j+1]*(j+1)/C;
        }
    }
} 

int main() {
    while (scanf("%d", &C), C) {
        scanf("%d %d", &N, &M); 
        if (N == 0 && M == 0) { 
            printf("%.3lf
", 1.);
            continue;
        }
        if ((N&1)^(M&1) || M > C || M > N) {
            printf("%.3lf
", 0.);
            continue;
        }
        if (N > 1000) {
            N = N & 1 ? 1001 : 1000;
        }
        DP();
        printf("%.3lf
", dp[N&1][N][M]);
    }
    return 0;    
}