← 返回题目列表

AtCoder · bitflyer2018_final_e

E. 公式和查询

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

配点 : 700 点

問題文

(, ), +, -, *, a 仅由组成的数式 S 被给出(详情请参阅问题文后半部分)。S 包含在 a 的个数 N 被记作。

N 个整数 a_1, ..., a_N 和 2 个整数 (b_i, x_i) 组成的 Q 个查询被给出,请处理这些查询。

查询:在给定的数式中,从左数第 b_i 个 a 的 x_i ,从左数 1, ..., b_i-1, b_i+1, ..., N 个 a 分别替换为 a_1, ..., a_{b_i-1}, a_{b_i+1}, ..., a_N 的数式的值,以及将 10^9+7 作为模同余的 0 以上 10^9+6 以下整数输出。

在此问题中给出的数式 S 用如下 BNF 表示法的 <expr> 符号表示。

<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term>
<term> ::= <value> | <term> '*' <value>
<value> ::= 'a' | '(' <expr> ')' 

制約

在给出的数式中包含的 a 的个数 N 被记作。

  • S 的长度为 200\,000 以下
  • S 可以用问题描述中的 BNF 表示法的 <expr> 符号表示。输出
  • 0 ≤ a_i < 10^9+7
  • 1 ≤ Q ≤ 10^5
  • 1 ≤ b_i ≤ N
  • 0 ≤ x_i < 10^9+7
  • x_i 是整数

入力

输入是按以下格式从标准输入给出的。

S
Q
a_1 ... a_N
b_1 x_1
:
b_Q x_Q

出力

Q 行。 i 行目 (1 ≤ i ≤ Q) 中输出第i 个查询的答案。例如,在第一个查询中,从左起


入力例 1

(a-(a))*a
4
0 1 2
1 1
1 2
2 1
1 4

出力例 1

0
2
1000000005
6

,从左起 1 个 a 使用 x_1 = 1 代入 2 个 a 使用 a_2 = 1 代入 3 个 a 使用 a_3 = 2 ,计算得到 (1-(1))*2 = 0 ,0 即为答案。

3 次数的查询中,从左边开始 1 个 a 使用 a_1 = 0 代入 2 个 a 使用 x_3 = 1 代入 3 个 a 使用 a_3 = 2 ,计算得到 (0-(1))*2 = -2 ,10^9+7 以...为模 -2 同余于... 0 以上 10^9+6 以下的整数是,10^9+5 即为答案。


入力例 2

(a)*a+((a+(a*(a))-(a)*a+a*a))*a
10
8 6 6 4 8 1 4 3 8 9
3 4
3 9
8 4
3 7
4 0
8 9
3 6
9 0
6 8
9 4

出力例 2

552
597
642
579
282
1002
570
354
318
462