Description

A toy box is a refrigerator filled with childhood delight. Like, weakness, struggle, hope … When such a sleeper is reawakened, what kind of surprises will be waiting?

M received her toy box as a birthday present from her mother. A jewellery designer would definitely spare no effort in decorating yet another priceless masterpiece as a starry firmament with exquisitely shaped gemstones. In addition, $L$ distinct locks secure the tiny universe of her lovely daughter: a hair clip featuring a flower design, a weathered feather pen, a balloon shaped like the letter M … each piece obscures a precious moment.

A few days ago, M rediscovered her toy box when she was reorganizing her bedroom, along with a ring of keys uniquely designed for the toy box. Attached to the key ring are $(L + K)$ keys, of which $L$ keys are able to open one of the $L$ locks correspondingly, while the other $K$ keys are nothing but counterfeits to discourage brute-force attacks. To remind the correspondence, M's mother adorned each key with a gemstone of a different type. However, passing days have faded M's memory away.

"… So I have to turn to you all," M said, while laying that ring of keys on the table.

K picked up the keys and examined them carefully. "The appearance of these keys unveils nothing fruitful. Thus, I am afraid that we shall inspect them sequentially."

Although everyone is willing to help M, nobody has a plan. Observing others' reactions, T suggested, "Let's play a game. Everyone tries a key in turn, and who opens the most locks is amazing."

$N$ members, including M herself, take turns to unlock the toy box recursively in the same order, until all the $L$ locks are unlocked. At each turn, the current member only selects a single key and tests it on exactly one of the locks. To open the toy box as soon as possible, every member chooses the key and the lock that maximize the probability of being a successful match. If there are multiple such pairs, a member will randomly choose one of such pairs with equal probability. Apparently, if a lock has been matched with a key, then neither the lock nor the key will be chosen again in following attempts.

Assume that at the very beginning, the probability that a lock can be opened by any key is equal. If everyone always tries the optimal pairs of keys and locks based on all the historical trials, what will the expected number of successful matches be for each member?

Input format

The only line of the input contains three integers, $N\ (1\le N\le 50)$, $L\ (1\le L\le 5000)$ and $K\ (0\le K\le 50)$ — the number of members participating in the game, the number of locks, and the number of counterfeit keys.

Output format

Output a single line with $N$ integers $E_1, \ldots, E_N$, where $E_i$ represents the expected number of successful matches, modulo $10^9 + 7$.

Formally, let $M = 10^9 + 7$. It can be proven that the exact $E_i$ can be expressed as an irreducible fraction $p_i/q_i$, where $p_i$ and $q_i$ are integers and $q_i \not\equiv 0 \pmod M$. Output the integer equal to $p_i\cdot q_i^{-1} \mod M$. In other words, output an integer $E_i$ such that $0\le E_i < M$ and $E_i \cdot q_i \equiv p_i \pmod M$.

Sample input 1

3 1 4

Sample output 1

800000006 800000006 400000003

Sample 1 explanation

When there is only $1$ lock, the strategy will always be choosing any key that no one has ever tried. Since there are $1 + 4 = 5$ keys in total, the probability that each member succesfully opens the lock will be $2/5, 2/5, 1/5$ respectively, which are also the expected numbers of successful matches.

Sample input 2

3 2 0

Sample output 2

500000004 1 500000004

Sample 2 explanation

There are exactly $2$ locks and $2$ keys, with each key corresponding to one of the locks. Without extra information, the first member randomly chooses a key and a lock with equal probabilities, for which the probability of success is $1/2$.

• If the first member succeeds, the second member will open the other lock with the other key.
• If the first member fails, then the key she selected can open the other lock, and the other key must correspond to the lock she chose. This information allows both the second and the third member to open a lock.

In conclusion, the expected numbers of successful matches will be:

$$ \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} $$

Sample input 3

25 2 5

Sample output 3

142857144 166666668 615646263 639455787 234126986 257936510 195918369 502040820 478316330 81264173 190523433 471438023 23809524 0 0 0 0 0 0 0 0 0 0 0 0

Sample input 4

4 102 9

Sample output 4

568832210 85779764 969938175 375449967

Source

清华大学学生算法协会 GitLink 仓库

【题目描述】

玩具箱承载着幼时的欢乐。喜爱、软弱、苦恼、希望……当沉睡的玩具箱再次被打开时，重见天日的宝物将会带来怎样的惊喜？

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】

3 1 4

【输出样例 1】

800000006 800000006 400000003

【样例 1 解释】

当只有 $1$ 把锁时，每个人的策略都是随机选择一把尚未有人试过的钥匙开锁。由于总共有 $1+4=5$ 把钥匙，每个人打开门的概率分别为 $2/5, 2/5, 1/5$，这也是每个人成功解锁的期望次数。

【输入样例 2】

3 2 0

【输出样例 2】

500000004 1 500000004

【样例 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} $$

【输入样例 3】

25 2 5

【输出样例 3】

142857144 166666668 615646263 639455787 234126986 257936510 195918369 502040820 478316330 81264173 190523433 471438023 23809524 0 0 0 0 0 0 0 0 0 0 0 0

【输入样例 4】

4 102 9

【输出样例 4】

568832210 85779764 969938175 375449967

【来源】

清华大学学生算法协会 GitLink 仓库