问题 1409. -- 背包弹夹平底锅

1409: 背包弹夹平底锅

时间限制:3000 ms 内存限制:128 MB
提交:62 解决:19
[ 提交][ 状态][ 讨论版]

题目描述

众所周知卢本伟是一名绝地科学家,但是他总是很谦虚地说:“我卢本伟没有开挂!”在网络赛中我们也发现了许多科学家,他们的高科技使得他们能写出和别人 100% 重复的代码。

一天,卢本伟捡了一个平底锅,并使用黑科技将它拆分成了一个背包和一个弹夹。卢本伟打开背包后发现其中有 n 个油纸包,每个油纸包里面都装了许多子弹,每个油纸包中的子弹都是一样的,但任意两个不同油纸包中的子弹类型都不相同。卢本伟注意到弹夹的容量是 m ,于是他决定用一种奇怪的方法将弹夹装满:每次等概率地抽取一个油纸包,然后从中拿一个子弹,装入弹夹中,再将油纸包放回背包。进行 m 次这样的操作后,他就可以装满弹夹。由于卢本伟的高科技,每种子弹都永远不会用完。

显然,通过这种方式装填弹夹后,弹夹中可能有 1, 2, ..., min(m, n) 种不同类型的子弹。卢本伟想到了一个问题:这 min(m, n) 种情况发生的概率分别是多少呢?

输入

输入包含多组数据,请处理到 EOF。

每组数据只有 1 行,包含 2 个整数 n, m。

由于卢本伟拥有无人能够理解的高科技,背包和弹夹都可能很大,有 1 <= n, m <= 10^5。

保证各组数据的 min(n, m) 之和不超过 2 * 10^6。

输出

对于每组数据输出 1 行,包含 min(n, m) 个整数,用空格分隔(行末不要有多余空格),其中第 i 个即弹夹中子弹种类数恰好为 i 的概率对 998244353 的模。

由于输出的数比较多,请使用较快的输出方式。

样例输入

3 3

样例输出

443664157 665496236 887328314

提示

卢本伟牛逼!

对于样例,总共有 3^3 = 27 种情况,其中只有 1 种子弹的有 3 种,有 3 种子弹的情况有 3! = 6 种,剩下就是有 2 种子弹的情况,有 18 种。可见应该输出的概率为 1/9,2/3,2/9。

严格来说,PUBG 中步枪的供弹具是弹匣(xia)而非弹夹(jia),本题为了和卢老爷的发音一致,都写成了弹夹。

来源

[ 提交][ 状态][ 讨论版]
Baidu
map