题意：
给一个文档， 这个文档由yes 、no 组成， 共有s个byte， 共有n个yes、no。
假设yes的个数为yes_num, no的个数为no_num。
将这n个数进行排列， 对于每个排列， 将其右移一个结果， 并在最左端补上yes， 再将其与原排列进行对比， 看有多少个不同的。
计算所有排列中 不同结果的平均次数。
思路：
可能题意说的不是很清楚， 这里抽象一下， 将yes用1代替， no用0代替。
当n = 3, s = 7时， 也就是2个0 一个1， 有下面三种排列
100, 010, 001
对于每种排列的处理：
100
110 不同的只有一个， 有三种情况， 每种情况抽中的概率是1/3 所以 当前情况的期望就是 1/3 * 1
010
101 不同的有三个， 当前情况的期望是1/3 * 3
001
100 不同的有两个，当前情况的期望是1/3 * 2
so, 总的期望就是1/3 * （1+3+2） = 6 / 3 = 2
将原排列进行整理下， 会发现一个现象。
每种排列的次数就是原排列中有多少个相邻不同的数字， 如果最左端是0， 那么还要 + 1 （因为左端要补上1， 和0 不同 所以要加1）
此时可以发现， 当前状态的期望数其实和上一状态是有关系的。
假设dp[i][j][flag]为当前为第i位， 前面有j个1(yes)， 上一状态（第i + 1 位） 是flag(0 == no, 1 == yes)。
那么， flag 要么为0， 要么为一， 也即 第i + 1位的状态。
{……j 个 yes……} flag k {…………}， k为第i + 2 位的状态。
dp[i][j][flag] = (dp[i+1][j][0] + (flag != 0))* p_no + (dp[i + 1][j + 1] + (flag != 1)) * p_yes.
也有大神推出公式了， 不过在下实在推不出来 囧 坐等大神解答。
公式：（2.0 * yes_num * no_num + no_num）/(yes_num + no_num)
加一段递归代码用以理解状态转移方程。
double dp(int n, int y, int a)
{
if (n == ) // There are no options to choose
return ;
double p_no = (n - y) / (double) n;
double p_yes = y / (double) n;
double ans = ;
if (y < n)
ans += (dp(n - , y, ) + (a != )) * p_no;
if (y > )
ans += (dp(n - , y - , ) + (a != )) * p_yes;
return ans;
}
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 5050
int n, s;
double dp[][MAXN][];// 0 --> NO, 1 --> yes
int yes_num, no_num;
int kcase = ;
void solve()
{
memset(dp, , sizeof(dp));
yes_num = s - * n;
no_num = n - yes_num;
for(int i = ; i <= n + ; i ++)
for(int j = ; j <= min(i, yes_num); j ++)
{
double p_yes = j * 1.0 / i;
double p_no = (i - j) * 1.0 / i; if(j - >= )
{
dp[i % ][j][] = dp[(i + ) % ][j - ][] * p_yes + (dp[(i + ) % ][j][] + 1.0) * p_no;
dp[i % ][j][] = (dp[(i + ) % ][j - ][] + 1.0) * p_yes + dp[(i + ) % ][j][] * p_no;
}
else
{
dp[i % ][j][] = (dp[(i + ) % ][j][] + 1.0) * p_no;
dp[i % ][j][] = dp[(i + ) % ][j][] * p_no;
}
}
printf("Case %d: %.7lf\n", ++kcase, dp[n % ][yes_num][]);
}
void solve_()
{
memset(dp, , sizeof(dp));
yes_num = s - * n;
no_num = n - yes_num; for(int i = n - ; i >= ; i --)
for(int j = min(i, yes_num); j >= && (i - j <= no_num); j --)
{
double p_yes = (yes_num - j) * 1.0 / (n - i);
double p_no = (no_num - (i - j)) * 1.0 / (n - i); if(j + <= yes_num)
{
dp[i % ][j][] = (dp[(i + ) % ][j + ][] + 1.0) * p_yes + dp[(i + ) % ][j][] * p_no;
dp[i % ][j][] = dp[(i + ) % ][j + ][] * p_yes + (dp[(i + ) % ][j][] + 1.0) *p_no;
}
else
{
dp[i % ][j][] = p_yes + dp[(i + ) % ][j][] * p_no;
dp[i % ][j][] = (dp[(i + ) % ][j][] + 1.0) *p_no;
}
}
printf("Case %d: %.7lf\n", ++kcase, dp[][][]);
} int main()
{
int T;
scanf("%d", &T);
while(T --)
{
scanf("%d %d", &n, &s);
solve_();
}
return ;
}