问题 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),本题为了和卢老爷的发音一致,都写成了弹夹。
来源
[
提交][
状态][
讨论版]