UVa 11118 Prisoners Boxes and Pieces of Paper

题目描述有n nn个囚犯n nn为偶数和n nn个黑盒子每个盒子中随机放有一个囚犯的名字。游戏规则如下囚犯事先可以商量策略但不知道盒子的排列。狱警随机排列盒子然后依次叫囚犯进入房间A AA。每个囚犯最多可以打开n / 2 n/2n/2个盒子如果找到自己的名字则进入房间C CC无法与外界通信否则本轮立即失败。如果所有囚犯都找到了自己的名字本轮获胜全体释放。如果失败第二天重新开始新的一轮。求最优策略下一轮游戏获胜的概率。获胜所需轮数的期望值。题目分析这是一个经典的“囚犯与盒子”谜题100 prisoners problem \texttt{100 prisoners problem}100 prisoners problem。若囚犯随机选择盒子获胜概率为( 1 / 2 ) n (1/2)^n(1/2)n几乎为0 00。但存在一个巧妙的策略将获胜概率提高到约1 − ln ⁡ 2 ≈ 0.30685 1 - \ln 2 \approx 0.306851−ln2≈0.30685。最优策略描述囚犯事先将盒子从1 11到n nn编号每个人也有一个唯一的编号例如从1 11到n nn。当囚犯i ii进入房间时他首先打开编号为i ii的盒子查看里面的名字假设名字对应编号j jj。然后他打开编号为j jj的盒子以此类推直到找到自己的名字或打开n / 2 n/2n/2个盒子为止。这相当于将盒子视为一个映射f : { 1 , … , n } → { 1 , … , n } f: \{1,\dots,n\} \to \{1,\dots,n\}f:{1,…,n}→{1,…,n}其中f ( k ) f(k)f(k)表示第k kk个盒子中放的是哪个囚犯的名字。由于名字互不相同这个映射是置换 \texttt{置换}置换permutation \texttt{permutation}permutation。每个囚犯i ii从i ii出发沿着置换的边i → f ( i ) → f ( f ( i ) ) → ⋯ i \to f(i) \to f(f(i)) \to \cdotsi→f(i)→f(f(i))→⋯行走寻找自己。获胜条件囚犯i ii能成功找到自己的名字当且仅当i ii所在的循环长度≤ n / 2 \le n/2≤n/2。因为沿着循环走最多走完整个循环就会回到i ii而i ii允许走n / 2 n/2n/2步所以只要循环长度不超过n / 2 n/2n/2就能找到。因此所有囚犯都成功⟺ \iff⟺置换中不存在长度大于n / 2 n/2n/2的循环。失败概率计算随机置换中包含一个长度恰好为k kk的循环的概率是多少长度为k kk的循环有( k − 1 ) ! (k-1)!(k−1)!种内部排列选择k kk个元素有( n k ) \binom{n}{k}(kn​)种方式剩余n − k n-kn−k个元素可任意排列( n − k ) ! (n-k)!(n−k)!种。所以包含一个特定长度为k kk的循环的排列数为( n k ) ⋅ ( k − 1 ) ! ⋅ ( n − k ) ! n ! k \binom{n}{k} \cdot (k-1)! \cdot (n-k)! \frac{n!}{k}(kn​)⋅(k−1)!⋅(n−k)!kn!​因此随机排列中存在一个长度为k kk的循环的概率为1 / k 1/k1/k注意这里“存在”指的是某个特定循环实际上要小心不同k kk的循环可能同时存在但长度 n/2 的循环至多只有一个因为两个这样的循环长度和 n不可能。所以长度为k n / 2 k n/2kn/2的循环存在的概率恰好是1 / k 1/k1/k。于是P lose ∑ k n / 2 1 n 1 k P_{\text{lose}} \sum_{k n/2 1}^{n} \frac{1}{k}Plose​kn/21∑n​k1​获胜概率P win 1 − ∑ k n / 2 1 n 1 k P_{\text{win}} 1 - \sum_{k n/2 1}^{n} \frac{1}{k}Pwin​1−kn/21∑n​k1​期望轮数每一轮是独立的获胜概率为P win P_{\text{win}}Pwin​因此获胜所需轮数服从几何分布期望为E 1 P win E \frac{1}{P_{\text{win}}}EPwin​1​参考代码// Prisoners Boxes and Pieces of Paper// UVa ID: 11118// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intT;scanf(%d,T);for(intcaseNo1;caseNoT;caseNo){intn;scanf(%d,n);doubleloseProb0.0;// 累加长度大于 n/2 的循环的概率for(intkn/21;kn;k)loseProb1.0/k;doublewinProb1.0-loseProb;doubleexpectedRounds1.0/winProb;// 输出精度保证 8 位小数printf(Case #%d: %.8f %.8f\n,caseNo,winProb,expectedRounds);}return0;}