开始的时候我没有考虑1/2的概率，直接一波组合数，然后WA
后来去看题解发现我们可以反过来想，求最后两个人不一样的情况
这个时候肯定会抛到最后的
所以每一种可能就是（0.5）^(n - 2),然后一共有C（n-2，n/2-1）种
乘起来就ok了。
但是这样会超时而且结果太大
所以我们可以尝试递推
通过计算可以发现d[i+2] = d[i] * (i-1) / i
所以就递推出所有值然后直接输出就好了。
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112345;
double d[MAXN];void init()
{d[2] = 1.0;REP(i, 2, MAXN)d[i+2] = d[i] * (i-1) / i;
}int main()
{init();int T, n;scanf("%d", &T);while(T--){scanf("%d", &n);printf("%.4lf\n", 1 - d[n]);}return 0;
}