https://vjudge.net/problem/UVA-557
题意：
n个人，n/2个牛肉煲，n/2个鸡肉堡
每次抛硬币，根据正反决定每个人吃什么汉堡
如果某一个汉堡被选完了，就不抛了
问最后两个人吃到同种汉堡的概率是多少
有抛硬币，想办法去掉抛硬币的干扰
要么都抛，要么都不抛
后者不大可能，考虑前者
如果前n-2个人都抛硬币，那么前n-2个人中，
有（n-2）/2 个人吃到牛肉煲，剩下的吃到鸡肉堡
所以，正难则反
计算最后两个人吃到不同种汉堡的概率
a[n]表示有n个人，最后两个人吃到不同汉堡的概率
a[n]=C（n-2，n/2-1）* （1/2）^（n-2）
C（n-2，n/2-1） 是所有可能情况有多少种
（1/2）^（n-2）n-2个人都要抛硬币，概率1/2
n很大，不能直接算组合数
考虑递推
#include<cstdio> #define N 100001 using namespace std; double a[N]; int main() { a[2]=1; for(int i=4;i<N;i+=2) a[i]=a[i-2]*(i-3)/(i-2); int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%.4lf ",1-a[n]); } }