题意无比诡异。 http://acm.timus.ru/problem.aspx?space=1&num=1716

俄罗斯的英文简直把我吓尿。

题意是对于输入：X1X2X3X4(Xi为YES或NO)

装变为              Y X1X2X3

然后问xi对应的错误的期望个数。 每种情况都是等概率的。

然后用dp做

dp[i][j][k](i表示第i位的情况，j表示1-i位中有多少个YES，k表示第i为是YES还是NO，是YES则为0，是NO则为1)

转移方程：

初始化: dp[1][1][0]= x / n;

　　　　dp[1][0][1]= y/ n; (其中x表示YES的总个数，y表示NO的总个数)

　　　　ans = dp[1][0][1];//最开始为N的直接加入

转移：　　dp[i+1][j][1]=(dp[i][j][1]+dp[i][j][0])*(y-i+j)/(n-i)

　　　　　dp[i+1][j+1][0]=(dp[i][j][1]+dp[i][j][0])*(x-i)/(n-i)

　　　　　ans += dp[i][j][0]*(y-i+j)/(n-i)+dp[i][j][1]*(x-i)/(n-i)  //加上由1->0的期望和0->1的期望。

// // main.cpp // timus1716 // // Created by 陈加寿 on 16/2/29. // Copyright © 2016年 chenhuan001. All rights reserved. //  #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; #define N 5005 long double dp[2][N][2]; #define eps 1e-11 int main(int argc, const char * argv[]) { int n,s; cin>>n>>s; long double x=s-2*n; long double y=n-x; int a=0; dp[a][1][0] = x/n; dp[a][0][1] = y/n; long double ans=dp[a][0][1]; long double tmp,tx,ty; for(int i=1;i<n;i++) { // for(int j=max(0,i-3*n+s);j<=min(i,s-2*n);j++) // { // dp[a^1][j][0]=dp[a^1][j][1]=0; // } for(int j=max(0,i-3*n+s);j<=min(i,s-2*n);j++) { tx=(x-j)/(n-i); ty=(y-i+j)/(n-i); //if(dp[a][j][0]!=0) //{ //dp[i][j][0] //if(i-j < y) //{ 
     tmp = dp[a][j][0]*ty; dp[a^1][j][1] += tmp; ans += tmp; //} //if(j != (s-2*n)) //{ 
     tmp =dp[a][j][0]*tx; dp[a^1][j+1][0] +=tmp; //} //} //if(dp[a][j][1]!=0) //{ //dp[i][j][1] //if(i-j < y) //{ 
     tmp=dp[a][j][1]*ty; dp[a^1][j][1] += tmp; //} //if(j!=s-2*n) //{ 
     tmp=dp[a][j][1]*tx; dp[a^1][j+1][0] += tmp; ans += tmp; //} //}  } memset(dp[a],0,sizeof(dp[a])); a^=1; } printf("%.6Lf\n",ans); return 0; }