UVA557 Burger 数论递推组合

在HUST做一个数论专场，看到这道题目过的人代码很短，就来水一下，一开始被鸟语坑了，题意是一共N个人（N肯定为偶数），Ben 和 Bill 排在最后，有N/2个汉堡和 N/2个奶酪，轮到每个人时扔硬币，扔到一面对应汉堡另一面对应奶酪，其中汉堡或者奶酪分所有人得到食物前已经被拿完了，就不再需要扔硬币了，问Ben 和 Bill 拿到相同食物的概率；

因为Ben 和 Bill 排在最后，所以可以反过来思考，那就是先求出Ben 和Bill拿到不同食物的概率为p,那么他们两个得到相同食物的概率就是1-p，要是Ben 和Bill 拿到不同的食物，那么在轮到他们两个之前是不会出现汉堡或者奶酪被拿完的情况，这样就比较好做了，前面人拿的情况总共为 2^(n-2)种，接下来通过组合数来求一下符合条件的情况数，除一下就可以求出概率了，这样公式是推出来了，可是数据很大，不可能直接求，这种情况一般都是递推式，很快我就轻易发现了当N为2时，也就是只有Ben 和 Bill两个人的时候，他们两个拿到不同东西的概率为1，这样递推式的边界值找到了，接下来就是寻找递推公式了，看了别人的做法递推式都是不一样的，因为大家对于N的看法是不一样的，但是万变不离其宗，都是通过组合数来求的，有个哥们的式子跟我的一样，我就直接复制他的图片了，公式打起来还是比较麻烦的：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // double p[100000+5]; void init() { p[2]=1.0; for(int i=4;i<100005;i+=2) p[i]=p[i-2]*(i-3)*1.0/(i-2)*1.0; } int main() { init(); int t; int n; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%.4lf\n",1-p[n]); } return EXIT_SUCCESS; }

UVA557 Burger 数论 递推组合