J - Product of Interval Score
Earlgray
3
s
1024
MB
600
点
問題文
本問題は I 問題と問題設定が似ていますが、スコアの計算方法、求める対象および制約の一部が異なります。
Esu君は $1$ 以上 $100$ 以下の整数が等確率で出るルーレットを使って次のように長さ $N$ の数列 $A=(A_1,A_2,\dots ,A_N)$ を定めます。
- ルーレットを $N$ 回回す。$i$ 回目のルーレットでは、 $p_i$ 以下の値が出たとき $A_i=1$ とし、そうでないとき $A_i=0$ とする。
なお、ルーレットを回す操作は毎回独立に行う。
その後、最終的な $A$ に応じてEsu君はスコアを獲得します。スコアの計算方法は以下の通りです。
- 初め、スコアは $1$ である。
- 各 $j = 1,2,\dots ,M$ について、 $A_{L_j},A_{L_j+1},\dots ,A_{R_j}$ が全て $1$ ならばスコアに $X_j$ を乗算する。
Esu君が獲得するスコアの期待値を $\textrm{mod} \ 998244353$ で求めてください。
期待値を $\textrm{mod} \ 998244353$ で求めるとは
求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 $\frac{P}{Q}$ で表したとき、 $Q\not\equiv 0 \ (\textrm{mod} \ 998244353)$ となることも証明できます。このとき、 $R\times Q\equiv P \ (\textrm{mod} \ 998244353)$ を満たす $0$ 以上 $998244353$ 未満の整数 $R$ が一意に定まります。この $R$ を求めてください。制約
- $1\le N,M\le 2\times 10^5$
- $0\le p_i\le 100$
- $1\le L_i \le R_i \le N$
- $0\le X_i < 998244353$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
$p_1$ $p_2$ $\dots$ $p_N$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_M$ $R_ M$ $X_M$
出力
答えを出力して改行せよ。
入力例 1
2 2
20 50
1 1 3
1 2 2
出力例 1
99824437
Esu君が定める $A$ としてあり得るもの、その確率およびスコアは以下の通りです。
- $A=(0,0)$ となる確率は $\frac{2}{5}$ で、このときのスコアは $1$ です。
- $A=(1,0)$ となる確率は $\frac{1}{10}$ で、このときのスコアは $3$ です。
- $A=(0,1)$ となる確率は $\frac{2}{5}$ で、このときのスコアは $1$ です。
- $A=(1,1)$ となる確率は $\frac{1}{10}$ で、このときのスコアは $6$ です。
$A$ のスコアの期待値は以下のように計算できます。
$\displaystyle \mu = 1\cdot \frac{2}{5} + 3\cdot \frac{1}{10} + 1\cdot \frac{2}{5} + 6\cdot \frac{1}{10} = \frac{17}{10}$
入力例 2
2 2
50 100
1 1 3
2 2 0
出力例 2
0
$A_2$ が必ず $1$ になるため、 $j=2$ のときに必ずスコアに $0$ が掛けられます。そのため、求める期待値は $0$ となります。
入力例 3
2 2
50 0
1 1 3
2 2 0
出力例 3
2
入力例 4
25 18
23 26 76 28 61 82 34 14 42 16 48 38 42 66 23 93 80 2 2 0 45 51 16 5 83
9 24 635844973
12 21 647730938
2 17 863209423
1 10 407082638
4 7 193445876
19 23 282312376
25 25 756524590
14 21 937404880
1 17 36381531
12 16 393993172
1 25 945599298
19 22 510783512
3 4 394212809
15 23 537671442
2 7 167345110
5 14 73691119
19 23 35337068
12 14 608121701
出力例 4
820745334