E - Homologous Recombination
問題文
東西方向に無限に続く道に $N$ 個の街があり、街には西から順に $1$ から $N$ までの番号がつけられています。
ペンギンの pengin2000 くんは、この道を赤か青のボールを持って $Q$ 回旅をします。
この道には魔法がかけられており、街 $i$ から $i+1\ (1 \leq i \leq N-1)$ まで移動すると、$\displaystyle \frac{p_i}{1000}$ の確率で、赤色のボールは青色に、青色のボールは赤色に、それぞれ色が変化します。
$j\ (1 \leq j \leq Q)$ 回目の旅では、はじめに青色のボールを持って、街 $s_j$ から $t_j$ までを最短距離で移動します。
各旅について、$t_j$ に着いたときに、持っているボールが赤色である確率を $\bmod\ 998244353$ で出力してください。
確率 $\bmod\ 998244353$ とは？
求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $\frac{P}{Q}$ で表したとき、 $Q \not\equiv 0\ (\bmod 998244353)$ となることも証明できます。 よって、 $R \times Q \equiv P\ (\bmod 998244353), 0 \leq R <998244353$ を満たす 整数 $R$ が一意に定まります。この $R$ を答えてください。制約
- $1 \leq N, Q \leq 2 \times 10^5$
- $0 \leq p_i \leq 1000$
- $1 \leq s_i < t_i \leq N$
- 入力はすべて整数である。
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($50$ 点)
- $p_i \in \lbrace 0,1000\rbrace$
- ($50$ 点)
- $p_1 = p_2 = \cdots = p_{N-1}$
- ($50$ 点)
- $s_i = 1$
- ($50$ 点)
- $N,Q \leq 2000$
- ($250$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$p_1$ $p_2$ $\dots$ $p_{N-1}$
$Q$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$
出力
$Q$ 行出力せよ。$i\ (1 \leq i \leq Q)$ 行目には、旅 $i$ についての答えの値を出力せよ。
6
500 200 1000 250 0
3
1 6
5 6
3 5
499122177
0
249561089
旅 $3$ では、$1 \times \frac{1}{4} = \frac{1}{4}$ の確率で色が $2$ 回変化して青色に、$1 \times \frac{3}{4} + 0 \times \frac{1}{4} = \frac{3}{4}$ の確率で色が $1$ 回変化して赤色に、$0 \times \frac{3}{4} = 0$ の確率で色が $0$ 回変化して青色になります。
求める確率は、$1$ 回変化する場合の $\frac{3}{4}$ です。$\bmod\ 998244353$ で表すと $249561089$ となります。
この入力は、部分点 4., 5. の制約を満たします。
6
1000 1000 1000 1000 1000
3
1 6
1 2
1 3
1
1
0
この入力では、街を移動するたびに必ず色が変化します。
旅 $1$, $2$ では、それぞれ $5$ 回、$1$ 回色が変化するため、最終的には赤色となります。赤色となる確率は $1$ です。
旅 $3$ では、$2$ 回色が変化するため、最終的には青色となります。赤色となる確率は $0$ です。
この入力は、すべての部分点の制約を満たします。