F - Random Gathering 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

N 個の皿が、皿 1, 皿 2,\ldots, 皿 N の順に左から並んでいます。 はじめ、皿 i\ (1\le i\le N) には A _ i 個の石が入っています。

この皿たちに対して M 回の操作を行います。 i 回目 (1\le i\le M) の操作では、2 つの整数 L _ i,R _ i が与えられ、次の操作を順に行います。

  • 皿 L _ i, 皿 L _ i+1,\ldots, 皿 R _ i の R _ i-L _ i+1 個の皿に入っている石をすべて皿の上から取り除く。
  • L _ i 以上 R _ i 以下の整数を一様ランダムに 1 つ取り、それを x とする。
  • 取り除いた石をすべて皿 x に乗せる。

i=1,2,\ldots,N について、M 回の操作がすべて終了したときに皿 i に置かれている石の個数の期待値を{}\bmod998244353 で求めてください。

期待値を{}\bmod{998244353} で求めるとは

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not\equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。期待値を{}\bmod{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 個の整数を 1 行に出力せよ。 i 番目 (1\leq i\leq N) には M 回の操作がすべて終了したときに皿 i に置かれている石の個数の期待値を{}\bmod998244353 で求め、出力せよ。

入力例 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

例えば、操作は次のように進みます。

  • 1 回目の操作で 4 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 30 個 ,10 個 ,40 個 ,150 個 ,0 個 ,0 個 ,20 個となる。
  • 2 回目の操作で 6 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 30 個 ,10 個 ,40 個 ,150 個 ,0 個 ,20 個 ,0 個となる。
  • 3 回目の操作で 2 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 0 個 ,250 個 ,0 個 ,0 個 ,0 個 ,0 個 ,0 個となる。
  • 4 回目の操作で 3 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 0 個 ,250 個 ,0 個 ,0 個 ,0 個 ,0 個 ,0 個となる。

すべての操作が終了したときに皿 1, 皿 2 に置かれている石の個数の期待値は 35 、皿 3, 皿 4, 皿 5, 皿 6, 皿 7に置かれている石の個数の期待値は 36 なので、35 35 36 36 36 36 36 を出力してください。

入力例 2

2 1
0 1
1 2

出力例 2

499122177 499122177

期待値を{}\bmod998244353 で求めることに注意してください。

すべての操作が終了したとき、どちらの皿についても \dfrac12 の確率で石が 1 つ置かれており、\dfrac12 の確率で石が 1 つも置かれていません。 よって、置かれている石の個数の期待値は \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

Score : 500 points

Problem Statement

There are N plates arranged from left to right as plate 1, plate 2,\ldots, plate N. Initially, plate i\ (1\le i\le N) contains A _ i stones.

You will perform M operations on these plates. In the i-th operation (1\le i\le M), two integers L _ i and R _ i are given, and the following operations are performed in order:

  • Remove all stones from the R _ i-L _ i+1 plates: plate L _ i, plate L _ i+1,\ldots, plate R _ i.
  • Uniformly randomly choose an integer between L _ i and R _ i, inclusive, and let it be x.
  • Place all the removed stones on plate x.

For i=1,2,\ldots,N, find the expected number, modulo 998244353, of stones placed on plate i when all M operations are completed.

Finding expected value modulo 998244353

It can be proved that the expected value you seek is always a rational number. Also, under the constraints of this problem, when that value is expressed as an irreducible fraction \frac{P}{Q}, it can be proved that Q \not\equiv 0 \pmod{998244353}. Therefore, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Finding the expected value modulo 998244353 means finding this R.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A _ 1 A _ 2 \ldots A _ N
L _ 1 R _ 1
L _ 2 R _ 2
\vdots
L _ M R _ M

Output

Output N integers separated by spaces on a single line. For the i-th (1\leq i\leq N), find the expected number, modulo 998244353, of stones placed on plate i when all M operations are completed, and output it.

Sample Input 1

7 4
30 10 40 10 50 90 20
4 6
5 7
1 6
3 7

Sample Output 1

35 35 36 36 36 36 36

For example, the operations proceed as follows:

  • In the first operation, 4 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 30, 10, 40, 150, 0, 0, 20, respectively.
  • In the second operation, 6 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 30, 10, 40, 150, 0, 20, 0, respectively.
  • In the third operation, 2 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 0, 250, 0, 0, 0, 0, 0, respectively.
  • In the fourth operation, 3 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 0, 250, 0, 0, 0, 0, 0, respectively.

When all operations are completed, the expected number of stones on plates 1, 2 is 35, and the expected number of stones on plates 3, 4, 5, 6, 7 is 36, so output 35 35 36 36 36 36 36.

Sample Input 2

2 1
0 1
1 2

Sample Output 2

499122177 499122177

Note that you need to find the expected value modulo 998244353.

When all operations are completed, for both plates, there is a \dfrac12 probability that one stone is placed, and a \dfrac12 probability that no stone is placed. Therefore, the expected number of stones placed is \dfrac12. We have 499122177\times2\equiv1\pmod{998244353}, so output 499122177 499122177.

Sample Input 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

Sample Output 3

449356308 449356308 449356308 449356308 449356308 648148154 648148154 648148154 648148154 648148154 648148154 643863031 643863031 643863031 643863031