UVa 557 汉堡

https://vjudge.net/problem/UVA-557

题意：

有n个牛肉堡和n个鸡肉堡给2n个孩子吃。每个孩子在吃之前都要抛硬币，正面吃牛肉堡，反面吃鸡肉堡。如果剩下的所有汉堡都一样，则不用抛硬币。求最后两个孩子迟到相同汉堡的概率。

思路：

我们可以先计算出最后两个孩子迟到不一样的汉堡的概率，这样之前的2n-2个孩子都需要抛硬币。

易得此时的概率为

因为有n-1个孩子吃同一种汉堡，所有一共有C（n-1,2n-2）种不同的选择方法，每种方法的概率都是（1/2）^（2n-2）。这也就是一个全概率公式。

最后得出一个递推公式，

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = +;

 double p[maxn];

 void init()

 {

     p[]=;

     for(int i=;i<=maxn;i++)

     {

         p[i+]=(-./(*i))*p[i];

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int n;

     int t;

     scanf("%d",&t);

     init();

     while(t--)

     {

         scanf("%d",&n);

         printf("%.4f\n",-p[n/]);

     }

     return ;

 }