#P18274. The Mysterious Shop
The Mysterious Shop
The Mysterious Shop
瓦洛兰大陆之外有一家神秘商店,没有人知道店主是谁。每天刚开始时,商店中的物品都会重新随机生成。可能出现的物品重量分别为 :对于每一种重量,都独立地以 的概率出现恰好一件该重量的物品,否则没有该重量的物品。重新生成后,前一天的物品也不会保留。
初来乍到的 Kevin 想先买些好装备。他每天带着容量为 的口袋,第一个走进商店,按照如下策略购买:
按重量从大到小依次检查当天商店中的物品。如果某件物品放入口袋后,总重量不超过 ,就买下并放入口袋;否则跳过这件物品。一直检查到所有物品都已考虑。
由于当地特殊的付款方式,可以认为 Kevin 总能付得起他决定放入口袋的所有物品。
Kevin 想知道自己每天的运气如何。请对每个 ,计算一天内他最终带走物品的总重量恰好为 的概率。
输入格式
输入只有一行,一个整数 (),同时表示最大可能物品重量和口袋容量。
本题只有一个测试用例,输入开头没有测试用例数。
输出格式
输出一行,共 个整数。第 个整数表示最终带走总重量恰好为 的概率乘以 后,对 取模的结果。
可以证明,在取模之前这些值都是整数。等价地,输出 种等可能的商店物品集合中,分别有多少种使 Kevin 带走总重量 ,再对 取模。
样例 1
输入:
1
输出:
1 1
样例 2
输入:
2
输出:
1 1 2
样例 3
输入:
3
输出:
1 1 1 5
样例 4
输入:
10
输出:
1 1 1 2 2 3 5 13 45 180 771
样例说明
第二个样例 有四种等可能的商店物品集合:
| 商店中的物品重量集合 | Kevin 带走的物品重量集合 | 总重量 |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | ||
因此,最终总重量为 的概率依次是 。乘以 后,输出为 1 1 2。