配点 : 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 时完成。
- h 至
在带有 x 。然后执行以下操作之一:
替换为
- 操作完成时 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)