题目链接：

题意：m个1和n-m个0的全排列有SUM=n!/m!/(n-m)!种。对于每一种排列将其看做二进制数x,x右移一位左边补1得到y,将x^y中1的个数称作x的f值。求每个排列的f之和除以SUM。

思路：其实f值就是x中相邻位不同的个数（若x以0开始则再加1，因为它说左边补1）,比如f(001)=2,f(101)=2。。。。我们设f[i][j][1]表示前i位含有j个1每次右移左边补1的期望(也就是x以0开始的话加1)，f[i][j][0]表示前i位含有j个1每次右移左边补0的期望。则我们有转移方程：

f[i][j][1]=(f[i-1][j][0]+1)*(i-j)/i+f[i-1][j-1][1]*j/i  : f[i-1][j][0]表示左侧补0，补0后还是j个1，所以可以得到 i位j个1，那么f[i-1][j][0]有多少个就对答案贡献多少个f[i-1][j][0]+1,加1是因为f[i][j][1]是左侧补1；f[i-1][j-1][1] 表示左侧补1，得到i为j个1，但是左侧再补1时不再对答案有贡献。那么接下来就是计算f[i-1][j][0]和f[i-1][j-1][1]的个数分别为多少

f[i][j][0]=(f[i-1][j-1][1]+1)*j/i+f[i-1][j][0]*(i-j)/i类似

 

#include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std;  struct node {     int n,m,id;	 double ans; };  int C; double f[2][5005][2]; node a[15];  int cmp(node a,node b) {     if(a.n!=b.n) return a.n
         
          C) return;             f[next][j][0]+=f[cur][j][0]*(i+1-j)/(i+1);             f[next][j][1]+=(f[cur][j][0]+1)*(i+1-j)/(i+1);             f[next][j+1][0]+=(f[cur][j][1]+1)*(j+1)/(i+1);             f[next][j+1][1]+=f[cur][j][1]*(j+1)/(i+1);         }         cur^=1;         next^=1;     } }   int main() {     scanf("%d",&C);     int i,n,m;     for(i=1;i<=C;i++)     {         scanf("%d%d",&n,&m);         a[i].n=n;         a[i].m=m-n-n;         a[i].id=i;     }     sort(a+1,a+C+1,cmp);     DP();	 sort(a+1,a+C+1,cmp1);     for(i=1;i<=C;i++) printf("Case %d: %.6lf\n",i,a[i].ans);     return 0; }