P12061 [THUPC 2025 决赛] 喜爱之钥

玩具箱承载着幼时的欢乐。喜爱、软弱、苦恼、希望……当沉睡的玩具箱再次被打开时，重见天日的宝物将会带来怎样的惊喜？ M 就有一个这样的玩具箱，那是身为宝石设计师的母亲送给她的生日礼物。精心打磨的宝石像夜空中的繁星一般点缀着玩具箱，而玩具箱上更有造型各异的 $L$ 把锁严防死守着宝贝女儿的小宇宙：花朵发夹、羽毛笔、字母 M 造型的气球……每一件都浓缩着 M 的回忆。 前几天，M 在整理房间时翻出了这个玩具箱，以及一串专门为这个玩具箱打造的钥匙。钥匙串上共挂着 $(L+K)$ 把钥匙，其中有 $L$ 把钥匙，每把分别可以打开其中一把锁；而剩下的 $K$ 把钥匙仅仅是增加暴力破解难度的干扰项。为了方便记忆，M 的母亲在设计钥匙时，给每一把钥匙镶嵌了一颗不同的宝石，可惜 M 已经忘记了正确的对应关系。 “……所以我只好向大家求助了。” M 说着把手里的钥匙串摆在了桌面上。 K 拿起了钥匙串仔细端详。“仅凭外表似乎无法推断出任何有用的信息，恐怕只能逐把尝试。” 虽然大家都愿意帮助 M，但是面对这么多把钥匙，不免感到无从下手。看着大家的反应，T 提议：“要不我们来玩个游戏吧。每个人按顺序试一把钥匙，最终打开最多锁的人最厉害。” 包括 M 在内，总共有 $N$ 个人按相同的顺序轮流尝试解锁玩具箱，直到 $L$ 把锁都被打开。每人每次操作时只选择一把钥匙，且只用这把钥匙试着打开其中一把锁。为了尽快打开玩具箱，所有人的策略都是尝试能最大化这次选择的钥匙打开这次选择的锁的概率的组合；如果有多种概率最大的钥匙和锁的组合，则等概率地选取任意一种这样的组合。显然，如果之前成功用一把钥匙打开了一把锁，那么之后所有人在尝试的时候，都不会再选择相同的钥匙或者相同的锁。 假设在最开始的时候，任意一把钥匙打开任意一把锁的概率都相等。如果每个人都能根据之前尝试的所有钥匙和锁的组合，选择最优的组合进行尝试，那么每个人成功解锁的期望次数分别是多少？

输入仅一行，包括三个非负整数 $N\ (1\le N\le 50), L\ (1\le L\le 5000), K\ (0\le K\le 50)$，分别表示参加游戏的人数，锁的数量和假钥匙的数量。

输出一行 $N$ 个非负整数 $E_1, \cdots, E_N$，其中 $E_i$ 表示按顺序第 $i$ 个人成功解锁的期望次数。显然 $E_i$ 是有理数；不妨假设其化为最简分式后的形式为 $p_i/q_i$（即其中 $p_i, q_i$ 互质），则 $E_i$ 为满足 $q_i E_i\equiv p_i \pmod{10^9+7}$ 和 $0\le E_i < 10^9+7$ 的整数解。可以证明，在本题数据范围下，各 $E_i$ 存在且唯一。

### 样例 #1 解释 当只有 $1$ 把锁时，每个人的策略都是随机选择一把尚未有人试过的钥匙开锁。由于总共有 $1+4=5$ 把钥匙，每个人打开门的概率分别为 $2/5, 2/5, 1/5$，这也是每个人成功解锁的期望次数。 ### 样例 #2 解释 此时有 $2$ 把锁和 $2$ 把钥匙，每把钥匙恰好可以打开其中一把锁。由于没有任何已知信息，第 $1$ 个人只能随机选择一把钥匙和一把锁，此时成功解锁的概率为 $1/2$。 - 如果第 $1$ 个人打开了这把锁，那么第 $2$ 个人可以直接用另外一把钥匙打开另外一把锁。 - 如果第 $1$ 个人没有打开这把锁，那么第 $1$ 个人选择的钥匙一定对应另一把锁，且另一把钥匙一定可以打开第 $1$ 个人选择的锁。根据这个信息，第 $2$ 个人和第 $3$ 个人可以各打开一把锁。 综上所述，每个人成功解锁的期望次数分别为 $$ \begin{split} E_1 &= \frac{1}{2}\times 1 + \frac{1}{2}\times 0 = \frac{1}{2} \equiv 500,000,004 \pmod {10^9+7},\\ E_2 &= \frac{1}{2}\times 1 + \frac{1}{2} \times 1 = 1,\\ E_3 &= \frac{1}{2}\times 0 + \frac{1}{2} \times 1 = \frac{1}{2} \equiv 500,000,004\pmod {10^9+7}. \end{split} $$ ### 来源与致谢 来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 。