博客

这个题向我充分展示了数学的简洁之美。

自己做的时候是从正面做的， 推出了个公式 ∑ (1/2)^(2n-k)*C(2n-k-1, n-k) (2<=k<=n,  n是总人数的一半)。 结果这个公式超时不说， 可以打表， 但精度不够， 大概2000+就不行了。 又发现一个规律可以把时间降到o(n)， 但是精度损失更大。

还是得看题解， 都是反着求得：已确定最后俩个人的汉堡是不一样的， 那么前面每次都会抛硬币， 概率为(1/2)^(n-2), (n是总人数， 下同)， 选(n-2)/2个人拿同一种汉堡， 则剩下的人拿另一种， 组合数为C(n-2, (n-2)/2)， 答案就是

(1/2)^(n-2)*

C(n-2, (n-2)/2)。

这样做估计还是超时， 不过可以打表了。

还可以继续优化， 找出递推公式， 边界f(2)=1， f(n)=f(n-2)*(n-3)/(n-2)。 竟然可以这么简单。