题目描述题目要求计算在随机分发汉堡和芝士汉堡的过程中最后两个孩子Ben\texttt{Ben}Ben和Bill\texttt{Bill}Bill得到相同类型汉堡的概率。总共有nnn个孩子nnn为偶数其中一半汉堡、一半芝士汉堡。前n−2n-2n−2个孩子通过抛硬币决定得到哪种汉堡最后两个孩子得到剩余的汉堡。输入格式第一行一个整数nnn表示测试用例的数量。接下来nnn行每行一个偶数mmm2≤m≤1000002 \le m \le 1000002≤m≤100000表示包括Ben\texttt{Ben}Ben和Bill\texttt{Bill}Bill在内的孩子总数。输出格式对于每个mmm输出一行一个概率保留四位小数。样例输入3 6 10 256输出0.6250 0.7266 0.9500题目分析本题的核心是计算最后两个孩子得到相同汉堡的概率。概率公式设总共有2k2k2k个汉堡kkk个汉堡kkk个芝士汉堡前2k−22k-22k−2个孩子通过抛硬币选择。最后两个孩子得到相同汉堡当且仅当在前2k−22k-22k−2次选择中汉堡和芝士汉堡各被选走了k−1k-1k−1个。概率为P1−(2k−2k−1)22k−2 P 1 - \frac{\binom{2k-2}{k-1}}{2^{2k-2}}P1−22k−2(k−12k−2​)​或者直接计算分子(2k−2k−1)/22k−2\binom{2k-2}{k-1} / 2^{2k-2}(k−12k−2​)/22k−2为最后两个孩子得到不同汉堡的概率所以相同概率为111减去该值。递推计算由于kkk最大为500005000050000直接计算组合数可能溢出可以使用递推Psame1−∏i1k−12i−12i P_{\text{same}} 1 - \prod_{i1}^{k-1} \frac{2i-1}{2i}Psame​1−i1∏k−1​2i2i−1​预计算所有kkk的乘积然后输出111减去对应值。复杂度分析预计算O(50000)O(50000)O(50000)每个查询O(1)O(1)O(1)。代码实现// Burger// UVa ID: 557// Verdict: Accepted// Submission Date: 2016-08-21// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);// Bernoulli trialdoubleprobability[50001]{1};for(inti1;i50000;i)probability[i]probability[i-1]*(longdouble)(2*i-1)/(longdouble)(2*i);intcases,n;cincases;for(intc1;ccases;c){cinn;coutfixedsetprecision(4)(1-probability[n/2-1])\n;}return0;}