#P17796. Perpetual Subtraction

Perpetual Subtraction

CF923E Perpetual Subtraction

题目描述

最初黑板上写有一个数字 xx。你需要重复以下操作若干次:

  1. 取下当前黑板上的数字 xx 并擦除;
  2. 从区间 [0,x][0,x](包含 xx)中均匀随机选择一个整数,并将其写在黑板上。

给定初始数字的概率分布和操作次数,求经过 MM 次操作后,最终数字的概率分布。

输入格式

第一行包含两个整数 NN(1≤N≤1051 \le N \le 10^{5})——黑板上可能写下的最大数字,以及 MM(0≤M≤10180 \le M \le 10^{18})——需要执行的操作次数。

第二行包含 N+1N+1 个整数 P0,P1,...,PNP_{0},P_{1},...,P_{N}(0≤Pi<9982443530 \le P_{i} < 998244353),其中 PiP_{i} 表示初始数字为 ii 的概率。若概率为最简分数 P/QP/Q,则 Pi≡PQ−1(mod998244353)P_{i} \equiv P Q^{-1} \pmod{998244353}。保证所有 PiP_{i} 之和模 998244353998244353 等于 11。

输出格式

输出一行共 N+1N+1 个整数,第 ii 个数 RiR_{i} 表示经过 MM 次操作后最终数字为 ii 的概率。概率可表示为最简分数 P/QP/Q,你需要输出 Ri≡PQ−1(mod998244353)R_{i} \equiv P Q^{-1} \pmod{998244353}。

输入输出样例 #1

输入 #1

2 1
0 0 1

输出 #1

332748118 332748118 332748118

输入输出样例 #2

输入 #2

2 2
0 0 1

输出 #2

942786334 610038216 443664157

输入输出样例 #3

输入 #3

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

输出 #3

822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326

说明/提示

在第一个样例中,初始数字为 22。经过一次操作后,最终数字为 00、11 或 22 的概率均为 1/31/3。

在第二个样例中,数字保持为 22 的概率为 1/91/9。有 1/91/9 的概率第一次保持为 22,第二次变为 11,有 1/61/6 的概率第一次变为 11,第二次保持为 11。其余情况下最终数字为 00。