Chocolate
状态转移方程为dp[i][j]=dp[i-1][j-1](t-j+1)/t+dp[i-1][j+1](j+1)/t;
上一次剩余j-1个或者剩余j+1个
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
double dp[1010][110];
int main()
{
int t,n,m;while(~scanf("%d",&t)&&t){
scanf("%d%d",&n,&m);if(m>n||m>t||(n%2==1&&m%2==0)||(n%2==0&&m%2==1)){
printf("0.000\n");continue;}if(n>1000){
if(n%2)n=1001;elsen=1000;}memset(dp,0,sizeof dp);dp[0][0]=1;for(int i=1;i<=n;i++){
dp[i][0]=dp[i-1][1]/t;dp[i][t]=dp[i-1][t-1]/t;for(int j=1;j<t;j++)dp[i][j]=dp[i-1][j-1]*(t-j+1)/t+dp[i-1][j+1]*(j+1)/t;}printf("%.3lf\n",dp[n][m]);}return 0;}