分数: 500 点
问题陈述
有 N 板从左到右排列为板 1, 板 2,\ldots, 板 N。 最初,板 i\ (1\le i\le N) 包含 A _ i 石头。
您将执行 M 在这些板块上进行操作。 在 i第次操作 (1\le i\le M),两个整数 给出 L _ i 和 R _ i ,依次执行以下操作:
- 移除所有石子 R _ i-L _ i+1 板: 板 L _ i, 板 L _ i+1,\ldots, 板 R _ i.
- 均匀随机选择一个整数 L _ i 和 R _ i,包容性,顺其自然 x.
- 将所有移除的石头放在盘子上 x.
对于 i=1,2,\ldots,N,找到期望的数字,取模 998244353,放置在盘子上的石头 i 当所有 M 操作已完成。
求期望值模 998244353
可以证明,你求的期望值总是有理数。另外,在这个问题的约束下,当该值表示为不可约分数时 \frac{P}{Q},可以证明 Q \not\equiv 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353。求期望值模 998244353 意味着找到这个 R.
约束
- 1\le N\le2\times10 ^ 5
- 1\le M\le2\times10 ^ 5
- 0\le A _ i\lt998244353\ (1\le i\le N)
- 1\le L _ i\le R _ i\le N\ (1\le i\le M)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A _ 1 A _ 2 \ldots A _ N L _ 1 R _ 1 L _ 2 R _ 2 \vdots L _ M R _ M
输出
输出 N 单行上用空格分隔的整数。 对于 i-th (1\leq i\leq N),找到期望的数字,取模 998244353,放置在盘子上的石头 i 当所有 M 运算完成,并输出。
示例输入 1
7 4 30 10 40 10 50 90 20 4 6 5 7 1 6 3 7
示例输出 1
35 35 36 36 36 36 36
例如,操作过程如下:
- 在第一次操作中, 选择 4 。盘子里的石头数量 1, 2,\ldots, 7 变为 30, 10, 40, 150, 0, 0, 20。
- 在第二次操作中, 6 。盘子里的石头数量 1, 2,\ldots, 7 变为 30, 10, 40, 150, 0, 20, 0。
- 在第三次操作中, 2 。盘子里的石头数量 1, 2,\ldots, 7 变为 0, 250, 0, 0, 0, 0, 0。
- 在第四次操作中, 3 。盘子里的石头数量 1, 2,\ldots, 7 变为 0, 250, 0, 0, 0, 0, 0。
当所有操作完成后,预计盘子上的石头数量 1, 2 is 35,以及盘子上的预期石头数量 3, 4, 5, 6, 7 is 36,所以输出 35 35 36 36 36 36 36.
示例输入 2
2 1 0 1 1 2
示例输出 2
499122177 499122177
请注意,您需要找到期望值模 998244353.
当所有操作完成后,对于两个板,都会有一个 \dfrac12 放置一颗石子的概率,并且 \dfrac12 没有放置石子的概率。
因此,预计放置的石子数量为 \dfrac12。
我们有 499122177\times2\equiv1\pmod{998244353},所以输出 499122177 499122177.
示例输入 3
15 10 61477244 450343304 812961384 836482955 280670539 405068748 318805088 304825858 518212597 316347783 589272551 505875419 944071276 364842194 5376942 2 11 5 9 8 15 6 7 6 8 1 2 1 10 4 9 12 15 6 11
示例输出 3
449356308 449356308 449356308 449356308 449356308 648148154 648148154 648148154 648148154 648148154 648148154 643863031 643863031 643863031 643863031