在给一个长度为n的数组排序过程中，z发现给打乱一个数组的顺序非常有序。Z用如下的方法来打乱一个数组的顺寻。
（1）选择一个数 k ，表示共交换 k次
（2）在 每次交换中，zakir每次随机选择两个不同位置的数，然后将他们的位置交换
这时zakir 突然想知道，对于给定的一个位置a上的数字，经过k次交换后最终被交换到 b位置的概率有多大？
Input
每行包含 4个数 n , k , a ,b 意义如上所述
2<=n<=1000 1<=k<=100000 0<= a < n 0<=b <n (下标从0开始)
以EOF结束
Output
一个小数，表示最后的概率，保留小数点后6位有效数字
Sample Input
5 1 3 3
5 1 0 1
5 2 2 3
Sample Output
0.600000
0.100000
0.150000

#include<stdio.h>
double dy_1(int k,double p_b_b,double p_a_b);//递归函数
double dy_2(int k,double p_b_b,double p_a_b);//递归函数
int main()
{
    int n,k,a,b;
    double p_b_b,p_a_b,p_s;//以p开头的表示概率
   
    
    while((scanf("%d%d%d%d",&n,&k,&a,&b))!=EOF)
         {
         
          if(n==2)
            {
                  if(a==b){if(k%2==1)p_s=0;else p_s=1;}
                  else {if(k%2==1)p_s=1;else p_s=0;}
                  }       
          
          else 
          {
                p_b_b=(double)(n-2)/(double)n;p_a_b=2*(double)1/(double)(n*(n-1));
                if(a==b) p_s=dy_1(k,p_b_b,p_a_b);
                else  p_s=dy_2(k,p_b_b,p_a_b);
                }   
                    
          printf("%.6f\n",p_s);
          
          }
   
     return 0;
}
 

double dy_1(int k,double p_b_b,double p_a_b)
{
       if(k==1) return p_b_b;
       else return (dy_1(k-1,p_b_b,p_a_b)*p_b_b+(1-dy_1(k-1,p_b_b,p_a_b))*p_a_b);
}     
double dy_2(int k,double p_b_b,double p_a_b)           
{
       if(k==1) return p_a_b;
       else return (dy_2(k-1,p_b_b,p_a_b)*p_b_b+(1-dy_2(k-1,p_b_b,p_a_b))*p_a_b);
}