← 返回题目列表

AtCoder · pakencamp_2024_day3_1_g

G. 括号序列查询

中文机器翻译题面 查看原题

配点 : 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)