C - Continued Fraction
問題文
長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
$Q$ 個のクエリを処理してください。クエリは次の $2$ 種類です。
-
クエリ1 :
1 l r
次の値を求め、以下の形式に沿って出力してください。
$A_l + \cfrac{1}{A_{l+1} + \cfrac{1}{A_{l+2} + \cfrac{1}{\ddots + \cfrac{1}{A_r}}}}$
ただし、$l=r$ のとき、この値は $A_l$ とします。
この値を既約分数 $\frac{P}{D}$ として表します。ここで、 $D>0$ とします。
$D \equiv 0 \pmod{998244353}$ のときは-1を出力してください。そうでないときは、 $P \times D^{-1} \pmod{998244353}$ を出力してください。
ここで、$D^{-1}$ は法 $998244353$ における $D$ の逆元を表します。 -
クエリ2 :
2 i x
$A_i$ を $x$ に変更してください。
制約
- 入力はすべて整数
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i < 998244353$
- $1 \leq Q \leq 2 \times 10^5$
- $1$ 番目の形式のクエリについて、$1 \leq l \leq r \leq N$
- $2$ 番目の形式のクエリについて、$1 \leq i \leq N$
- $2$ 番目の形式のクエリについて、$1 \leq x < 998244353$
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1\ A_2\ \dots\ A_N$
$Q$
$query_1$
$query_2$
$\ \ \ \ \vdots$
$query_Q$
各クエリ $query_i$ は
$1\ l\ r$
又は
$2\ i\ x$
のいずれかの形式で与えられる。
出力
操作 1 l r が現れるたびに、その答えを $1$ 行に出力してください。
3
1 2 3
3
1 1 3
2 2 4
1 1 3
570425346
383940137
最初、数列は $A=(1,2,3)$ です。
-
$1$ 個目のクエリでは、$l=1,r=3$ なので、次の値を求めます。
$A_1 + \frac{1}{A_2 + \frac{1}{A_3}} = 1 + \frac{1}{2 + \frac{1}{3}}$
ここで、 $2 + \frac{1}{3} = \frac{7}{3}$ なので、
$1 + \frac{1}{\frac{7}{3}} = 1 + \frac{3}{7} = \frac{10}{7}$
したがって、 $P=10,\quad D=7$ です。 $D \not\equiv 0 \pmod{998244353}$ なので、
$10 \times 7^{-1} \equiv 570425346 \pmod{998244353}$ を出力します。 -
$2$ 個目のクエリでは、$A_2$ を $4$ に変更します。したがって、数列は $A=(1,4,3)$ になります。
-
$3$ 個目のクエリでは、次の値を求めます。
$A_1 + \frac{1}{A_2 + \frac{1}{A_3}} = 1 + \frac{1}{4 + \frac{1}{3}}$
ここで、 $4 + \frac{1}{3} = \frac{13}{3}$ なので、
$1 + \frac{1}{\frac{13}{3}} = 1 + \frac{3}{13} = \frac{16}{13}$
したがって、 $P=16,\quad D=13$ です。 $D \not\equiv 0 \pmod{998244353}$ なので、
$16 \times 13^{-1} \equiv 383940137 \pmod{998244353}$ を出力します。
3
1 2 499122176
1
1 1 3
-1
数列は $A=(1, 2, 499122176)$ です。
クエリでは、次の値を求めます。
$A_1 + \frac{1}{A_2 + \frac{1}{A_3}} = 1 + \frac{1}{2 + \frac{1}{499122176}}$
ここで、
$2 + \frac{1}{499122176} = \frac{2 \times 499122176 + 1}{499122176} = \frac{998244353}{499122176}$
です。したがって、全体の値は
$1 + \frac{1}{\frac{998244353}{499122176}} = 1 + \frac{499122176}{998244353} = \frac{1497366529}{998244353}$
となります。この分数は既約であり、分母は $D=998244353$ です。よって、 $D \equiv 0 \pmod{998244353}$ となるため、
答えとして -1 を出力します。