Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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