简要题意

有 $N$ 个人，$L$ 把锁和 $(L+K)$ 把钥匙。其中有 $L$ 把真钥匙，分别可以打开一把锁；另外 $K$ 把钥匙是假的，不能打开任何锁。

所有人按顺序尝试钥匙。每个人的策略都是最大化选择的钥匙打开选择的门的概率。如果有多种概率最大的组合，则等概率选择其中一种。

求打开所有锁之后每个人开锁次数的期望。

$1\le N\le 50$, $1\le L\le 5000$, $0\le K\le 50$

求解策略

为了解决这个问题，我们需要知道每个人具体会如何选择钥匙和锁。

显然，最开始的人不知道任何信息，所以只能随机选择一把钥匙和一把锁。

如果第一个人没有打开锁，第二个人有三种选法：选同一把钥匙开不同锁，选不同钥匙开同一把锁，选不同钥匙和锁。

选同一把钥匙开不同锁，或者选不同钥匙开同一把锁，解锁概率都是 $1/(L+K-1)$；选不同钥匙和锁的解锁概率是

$$\frac{1 - \frac{1}{L+K-1}}{L+K-1} = \frac{L+K-2}{(L+K-1)^2} < \frac{1}{L+K-1}$$

所以第二个人会以 $(L-1)/(2L+K-2)$ 的概率选同一把钥匙开不同锁，以 $(L+K-1)/(2L+K-2)$ 概率选不同钥匙开同一把锁。

结论

同理可以继续分析后续各人的策略。结论为：如果第二个人选择了同一把钥匙，则接下来每个人都会选择这把钥匙；如果第二个人选择了同一把锁，则接下来每个人都会选择这把锁。

不难想到记录 $f_i(l, k)$ 表示 $L=l, K=k$ 时第 $i$ 个人的期望开锁次数，则可以对 $f$ 进行 DP。

另一种做法是，记 $p_i(l, k)$ 表示已经打开了 $l$ 把锁，发现 $k$ 把假钥匙，轮到第 $i$ 个人进行首次尝试的概率（此时除了 $l$ 和 $k$ 以外没有任何额外信息，重置到所有组合等概率的状态），另外记 $E_i$ 表示答案。

出题人写的是后一种写法，验题人写的是前一种写法，都可以通过。

转移

因为决策有三类，所以转移分为三种：第一个人直接开锁，第二个人开锁（分相同钥匙还是相同锁讨论），后续其余人开锁（同样分类讨论）。

前两种转移都是 $O(1)$ 的，第三种转移如果直接做是 $O(L+K)$ 的，总复杂度 $O(NLK\cdot (L+K))$，不能通过本题。

推式子可知，对于第三种转移而言，恰是某一次尝试时解锁的概率是相等的。直观理解：多人抓阄，是每个人按顺序抓并直接打开，还是所有人先抓完再一起打开，并不影响每个人抽中的概率。

由此可知，我们只需要统计每个第三种转移中，每个人可以尝试多少次，再乘上相应的概率即可。这样可以将复杂度降低到 $O(NLK\cdot N)$，但仍然不能通过。

如果你常数足够小，有可能可以松过去

进一步优化

冷静分析：因为尝试是按顺序进行的，所以尝试的次数很平均。

• 如果尝试次数 $x$（如果是相同钥匙，就是剩余锁的数量；如果是相同锁，就是剩余钥匙的数量）恰好是 $N$ 的倍数，则每个人恰好试 $x/N$ 次。
• 否则，前 $x \mod N$ 个人可以试 $\lceil x/N \rceil$ 次，其余人可以试 $\lfloor x/N \rfloor$ 次。

因为相同尝试次数（也即相同转移系数）的极长连续段只有 $O(1)$ 个，所以可以用前缀和的方式，将第三种转移优化到 $O(1)$。总复杂度 $O(NLK)$，可以通过本题。