G - Bracket Sequence Queries Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

( または ) のみからなる文字列 S が与えられます。

また、Q 個のクエリが与えられます。i 番目のクエリでは正整数の組 (s_i,t_i) が与えられるので、以下の問題を解いてください。

  • s_i で初期化された変数 x と、長さ 0 の数列 h がある。以下の操作を 0 回以上好きな回数行う。
    • h に x を追加する。その後、以下のどちらかを行う。
      • x を x+1 で置き換える。
      • S の x+1 文字目から y 文字目までを取り出した文字列が正規括弧列であるような y を好きに選び、x を y で置き換える。この操作は x\leq |S|-1 のときのみ行うことができる。
  • 操作を終了したときに x=t_i となっているとき、最終的な h としてありうるものの個数を 998244353 で割ったあまりを求めよ。
正規括弧列とは？

正規括弧列とは、() である部分文字列を削除することを 0 回以上繰り返して空文字列にできる文字列を指します。

制約

  • S は ( または ) のみからなる長さ 1 以上 200000 以下の文字列
  • 1\leq Q\leq 200000
  • 0\leq s_i\lt t_i\leq |S| (1\leq i\leq Q)
  • Q,s_i,t_i は整数

入力

入力は以下の形式で標準入力から与えられる。

S
Q
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q

出力

Q 行出力せよ。

i 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

(()())
3
0 6
1 3
1 4

出力例 1

6
2
2

1 番目のクエリについて、最終的な h としてありうるものは以下の 6 通りです。

  • (0)
  • (0,1,5)
  • (0,1,3,5)
  • (0,1,3,4,5)
  • (0,1,2,3,5)
  • (0,1,2,3,4,5)