I - Sum of Interval Score
問題文
Esu君は $1$ 以上 $100$ 以下の整数が等確率で出るルーレットを使って次のように長さ $N$ の数列 $A=(A_1,A_2,\dots ,A_N)$ を定めます。
- ルーレットを $N$ 回回す。$i$ 回目のルーレットでは、 $p_i$ 以下の値が出たとき $A_i=1$ とし、そうでないとき $A_i=0$ とする。
なお、ルーレットを回す操作は毎回独立に行う。
その後、最終的な $A$ に応じてEsu君はスコアを獲得します。スコアの計算方法は以下の通りです。
- 初め、スコアは $0$ である。
- $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$
- $1\le X_i < 998244353$
- 入力はすべて整数
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($50$ 点)
- $N\le 18$
- ($150$ 点)
- $X_i = 1$
- $N,M\le 100$
- ($50$ 点)
- $X_i = 1$
- $N,M\le 3000$
- ($350$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$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$
出力
答えを出力して改行せよ。
2 2
20 50
1 1 2
1 2 1
149736654
Esu君が定める $A$ としてあり得るもの、その確率およびスコアは以下の通りです。
- $A=(0,0)$ となる確率は $\frac{2}{5}$ で、このときのスコアは $0$ です。
- $A=(1,0)$ となる確率は $\frac{1}{10}$ で、このときのスコアは $2$ です。
- $A=(0,1)$ となる確率は $\frac{2}{5}$ で、このときのスコアは $0$ です。
- $A=(1,1)$ となる確率は $\frac{1}{10}$ で、このときのスコアは $3$ です。
$A$ のスコアの期待値 $\mu$ は以下のように計算されます。
$\displaystyle \mu = 0\cdot \frac{2}{5} + 2\cdot \frac{1}{10} + 0\cdot \frac{2}{5} + 3\cdot \frac{1}{10} = \frac{1}{2}$
よって $A$ のスコアの分散は以下のように計算できます。
$\displaystyle (0-\mu)^2 \cdot \frac{2}{5} + (2-\mu)^2 \cdot \frac{1}{10} + (0-\mu)^2 \cdot \frac{2}{5} + (3-\mu)^2 \cdot \frac{1}{10} = \frac{21}{20}$
この入力は部分点 1., 4. の制約を満たします。
1 2
0
1 1 1
1 1 1
0
この入力は部分点 1., 2., 3., 4. の制約を満たします。
23 18
24 58 13 65 55 24 0 89 4 76 10 5 67 39 58 27 73 59 85 27 17 100 50
2 14 1
21 22 1
4 6 1
2 10 1
14 22 1
12 12 1
4 13 1
11 14 1
2 21 1
14 23 1
2 23 1
18 19 1
4 18 1
3 16 1
2 11 1
4 18 1
3 14 1
4 11 1
499961141
この入力は部分点 2., 3., 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
593228600
この入力は部分点 4. の制約を満たします。