分数: 550 点
问题陈述
给你一个整数序列 A = (A_1, A_2, \ldots, A_N) 长度 N.
我们将执行以下操作 A 为 i = 1, 2, \ldots, M 按此顺序。
- 首先,选择一个整数 L_i 和 R_i,包含在内,均匀随机,表示为 p.
- 然后,更改值 A_p 为整数 X_i.
对于最终序列 A 经过上述过程后,打印期望值,模 998244353,属于 A_i 对于每个 i = 1, 2, \ldots, N.
如何打印期望值模 998244353
可以证明,该问题所求的期望值总是有理数。此外,该问题的约束保证如果每个期望值都表示为不可约分数 \frac{y}{x},那么 x 不能被整除 998244353.
现在,有一个唯一的整数 z 之间 0 和 998244352,包含在内,这样 xz \equiv y \pmod{998244353}。报告此事 z.
约束
- 所有输入值均为整数。
- 1 \leq N, M \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq L_i \leq R_i \leq N
- 0 \leq X_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_N L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_M R_M X_M
输出
打印预期值 E_i 决赛 A_i 为 i = 1, 2, \ldots, N 格式如下,以空格分隔。
E_1 E_2 \ldots E_N
示例输入 1
5 2 3 1 4 1 5 1 2 2 2 4 0
示例输出 1
499122179 1 665496238 665496236 5
我们从初始状态开始 A = (3, 1, 4, 1, 5) 并执行以下两个操作。
- 第一个操作选择 A_1 or A_2 随机均匀,并将其值更改为 2.
- 然后,第二个操作选择以下之一 A_2, A_3, A_4 随机均匀,并将其值更改为 0.
因此,最终元素的期望值 A 是 (E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5).
示例输入 2
2 4 1 2 1 1 3 2 2 4 1 1 5 2 2 6
示例输出 2
5 6
示例输入 3
20 20 998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158 12 18 769877494 9 13 689822685 6 13 180913148 2 16 525285434 2 14 98115570 14 17 622616620 8 12 476462455 13 17 872412050 14 15 564176146 7 13 143650548 2 5 180435257 4 10 82903366 1 2 643996562 8 10 262860196 10 14 624081934 11 13 581257775 9 19 381806138 3 12 427930466 6 19 18249485 14 19 682428942
示例输出 3
821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158