← 返回题目列表

Codeforces · 923/E

E. 永久减法

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

黑板上最初写着一个数字x。您重复以下操作固定次数:

1. 将当前写在黑板上的数字 x 擦掉
2.从[0, x]范围内均匀随机选择一个整数,写在黑板上

给定初始数的分布和步数,确定最终数的分布。

输入

第一行包含两个整数,N (1 ≤ N ≤ 105) — 黑板上写的最大数字 — 和 M (0 ≤ M ≤ 1018) — 要执行的步骤数。

第二行包含 N + 1 个整数 P0, P1, ..., PN (0 ≤ Pi < 998244353),其中 Pi 描述起始数字为 i 的概率。我们可以将这个概率表示为不可约分数 P / Q,然后 $$P_i \equiv PQ^{-1} \pmod{998244353}$$。保证所有 Pi 之和等于 1(模 998244353)。

输出

输出单行 N + 1 个整数,其中 Ri 是 M 步后最终数字为 i 的概率。可以证明,概率总是可以表示为不可约分数 P / Q。要求您输出 $$R_i \equiv PQ^{-1} \pmod{998244353}$$。

示例

输入 #1

2 1
0 0 1

输出 #1

332748118 332748118 332748118

输入 #2

2 2
0 0 1

输出 #2

942786334 610038216 443664157

输入 #3

9 350
3 31 314 3141 31415 314159 3141592 31415926 314159265 649178508

输出 #3

822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326

注意

在第一种情况下,我们从数字 2 开始。一步之后,它将是 0、1 或 2,每个概率为 1/3。

在第二种情况下,数字仍为 2,概率为 1/9。以 1/9 的概率,在第一轮中保持 2,在下一轮中变为 1,以 1/6 的概率在第一轮中变为 1,并在第二轮中保持不变。在所有其他情况下,最终整数都是 0。