AT_abc332_f.[ABC332F] Random Update Query

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 。

对于 $A$ ，依次进行 $i = 1, 2, \ldots, M$ 的如下操作：

首先，从 $L_i$ 到 $R_i$ 之间的整数中等概率随机选取一个，记为 $p$ 。
然后，将 $A_p$ 的值修改为整数 $X_i$ 。

经过上述所有操作后，请输出最终 $A$ 中每个 $A_i$ 的期望值 $\bmod\ 998244353$ ，对于每个 $i = 1, 2, \ldots, N$ 。

期望值 $\bmod\ 998244353$ 的定义：本题中要求的期望值一定是有理数。并且，在本题的约束下，若将期望值表示为最简分数 $\frac{y}{x}$ ，则 $x$ 一定不会被 $998244353$ 整除。

此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$ ，满足 $xz \equiv y \pmod{998244353}$ 。请输出这个 $z$ 。

输入格式

输入以如下格式从标准输入读入。

$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$

输出格式

请输出最终每个 $A_i$ 的期望值 $E_i$ ，按照如下格式以空格分隔输出。

$E_1$ $E_2$ $\ldots$ $E_N$

输入输出样例

输入#1

输出#1

499122179 1 665496238 665496236 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

说明/提示

约束

输入的所有数均为整数。
$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$

样例解释 1

初始状态为 $A = (3, 1, 4, 1, 5)$ ，进行如下两次操作：

首先，第 1 次操作中， $A_1$ 和 $A_2$ 中的一个会被等概率选中，其值被改为 $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)$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页