题目链接：

　　比较水的DP，只是精度有点坑。f[i][j]表示放置i次后，桌子上有j个chocolate的概率。显然，f[i][j]=sum{f[i-1][j-1]*(c-j+1)/c+f[i-1][j+1]*(j+1)/c};但是如果不优化，会超时，注意到f方程式随着i的增大是收敛的，所以当n很大时，只要计算前面就可以了，大概1000足够。我做的时候是比较精度fbs(f[i][j]-f[i][j-2])<esp,这样求出来c=100时，大概只要500次，但WA了，证明还是不足够收敛。显然这里还可以用滚动数组优化。

1 //STATUS:C++_AC_110MS_180KB 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 #include
             
              11 #include
              
               12 using namespace std;13 #define LL __int6414 #define pdi pair
               
                15 #define Max(a,b) ((a)>(b)?(a):(b))16 #define Min(a,b) ((a)<(b)?(a):(b))17 #define mem(a,b) memset(a,b,sizeof(a))18 #define lson l,mid,rt<<119 #define rson mid+1,r,rt<<1|120 const int N=110,INF=0x3f3f3f3f,MOD=100000000;21 const double esp=0.000001;22 23 double f[2][N];24 int c,n,m;25 26 int main()27 {28 // freopen("in.txt","r",stdin);29 int i,j,p;30 while(~scanf("%d%d%d",&c,&n,&m) && c)31 {32 if(m>c || m>n || (n+m)&1){33 printf("0.000\n");34 continue;35 }36 mem(f,0);37 f[0][0]=p=1;38 if(n>1000)n=1000+(n&1);39 while(n--){40 f[p][0]=f[!p][1]/c;41 for(i=1;i<=c;i++)42 f[p][i]=f[!p][i-1]*(c-i+1)/c+f[!p][i+1]*(i+1)/c;43 p=!p;44 }45 46 printf("%.3lf\n",f[!p][m]);47 }48 return 0;49 }