← 返回题目列表

Codeforces · 2089/C2

C2. 点赞之键(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的差异在于,在此版本中,$$$k$$$ 可以为非零。只有解决了该问题的所有版本,您才能破解。

玩具盒是充满童年欢乐的冰箱。比如软弱、挣扎、希望……当这样的沉睡者被重新唤醒时,等待着的将会是怎样的惊喜?

M 收到了她母亲送给她的玩具盒作为生日礼物。珠宝设计师一定会不遗余力地用形状精美的宝石将又一件无价之宝的杰作装饰成星空。此外,$$$l$$$ 独特的锁保护了她可爱女儿的小宇宙:带有花朵图案的发夹、一支风化的羽毛笔、一个形状像字母 M 的气球……每件作品都掩盖了一个珍贵的时刻。

几天前,M在整理卧室时重新发现了她的玩具箱,还有一圈专门为玩具箱设计的钥匙圈。钥匙圈上附有 $$$(l + k)$$$ 钥匙,其中 $$$l$$$ 钥匙可以相应打开 $$$l$$$ 锁中的一把,而其他 $$$k$$$ 钥匙只不过是伪造的,以阻止暴力攻击。为了提醒信件的对应,M 的母亲在每把钥匙上都装饰了不同类型的宝石。然而,随着时间的流逝,M的记忆逐渐消失。

“……所以我必须求助于你们所有人,”M一边说,一边把钥匙圈放在桌子上。

K拿起钥匙,仔细检查。 “这些钥匙的出现并没有揭示任何成果。因此,恐怕我们将依次检查它们。”

虽然每个人都愿意帮助M,但没有人有计划。 T观察了其他人的反应,建议:“我们来玩一个游戏,每个人轮流尝试一把钥匙,谁打开的锁最多。” 太棒了."

$$$n$$$成员,包括M本人,轮流以相同的顺序递归地解锁玩具箱,直到所有$$$l$$$锁都被解锁。在每一轮中,当前成员仅选择一把钥匙并在其中一把锁上测试它。为了尽快打开玩具箱,每个成员都选择最大匹配成功概率的钥匙和锁。如果有多个这样的对,则成员将以相同的概率随机选择这样的对之一。显然,如果锁已经与钥匙匹配,那么在接下来的尝试中将不会再次选择锁和钥匙。

假设一开始,任何一把钥匙都能打开一把锁的概率是相等的。如果每个人总是根据所有历史尝试来尝试最佳的钥匙和锁对,那么每个成员的预期成功匹配次数是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

输入中唯一一行包含三个整数,$$$n$$$, $$$l$$$, $$$k$$$ ($$$1 \leq n \leq 100, 1 \leq l \leq 5000, 0 \leq k \leq 25$$$) ——参与游戏的会员数、锁数、假币数键。

保证所有测试用例的 $$$l$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一行,其中包含 $$$n$$$ 整数 $$$e_1, \ldots, e_n$$$,其中 $$$e_i$$$ 表示成功匹配的预期数量,模 $$$10^9 + 7$$$。

正式地,让 $$$M = 10^9 + 7$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$e_i$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$e_i \cdot q \equiv p \pmod{M}$$$ 。

示例

输入
复制

4
3 1 4
3 2 0
25 2 5
4 102 9

输出
复制

800000006 800000006 400000003
500000004 1 500000004
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
568832210 85779764 969938175 375449967

注意

对于第一个测试用例,只有 $$$1$$$ 锁,因此策略将始终选择没有人尝试过的任何密钥。由于总共有 $$$1 + 4 = 5$$$ 钥匙,因此每个成员成功开锁的概率分别为 $$$2/5, 2/5, 1/5$$$,这也是期望的成功匹配数。

对于第二个测试用例,恰好有 $$$2$$$ 锁和 $$$2$$$ 钥匙,每个钥匙对应于其中一把锁。在没有额外信息的情况下,第一个成员以相同的概率随机选择一把钥匙和一把锁,成功的概率为 $$$1/2$$$。

  • 如果第一个成员成功,第二个成员将用另一把钥匙打开另一把锁。
  • 如果第一个成员失败,那么她选择的钥匙可以打开另一把锁,而另一把钥匙必须与她选择的锁相对应。该信息允许第二和第三成员打开锁。

总之,成功匹配的预期数量为:

$$\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}。 \结束{分割}$$