No.510 二次漸化式

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 29
作問者 : はむこはむこ / テスター : ixmelixmel

3 ProblemId : 1316 / 出題時の順位表

問題文

漸化式で定義される数列$a_i, b_i (0 \leq i \leq n)$がある。

$a_{i+1} = x_i b_i^2 + a_i$
$b_{i+1} = y_i b_i + 1$
$a_0 = b_0 = 1$

$x_i, y_i (0 \leq i < n)$は$2 n$個の漸化式のパラメータである。これらの初期値は$0$である。
以下のクエリを$q$個処理せよ。

(1) $x$ $i$ $v$
$x_i$を$v$に変更する。
(2) $y$ $i$ $v$
$y_i$を$v$に変更する。
(3) $a$ $i$
$a_i$を$10^9+7$で割った余りを出力する。

入力

$n$
$q$
$query_1$
$\vdots$
$query_q$

入力は全て整数。

$1 \leq n \leq 100000$
$1 \leq q \leq 20000$

クエリx
x $i$ $v$
$0 \leq i < n$
$0 \leq v \leq 100000$

クエリy
y $i$ $v$
$0 \leq i < n$
$0 \leq v \leq 100000$

クエリa
a $i$
$0 \leq i \leq n$

クエリaは少なくとも1つあることが保証される。

出力

各クエリaのあとに改行してください。

サンプル

サンプル1
入力
2
7
a 2
x 1 1
y 0 3
y 1 2
a 2
y 0 0
a 2
出力
1
17
2

1回目のクエリaでは、$a_0 = 1, a_1 = 1, a_2 = 1, b_0 = 1, b_1 = 1, b_2 = 1$です。
2回目のクエリaでは、$a_0 = 1, a_1 = 1, a_2 = 17, b_0 = 1, b_1 = 4, b_2 = 9$です。
3回目のクエリaでは、$a_0 = 1, a_1 = 1, a_2 = 2, b_0 = 1, b_1 = 1, b_2 = 3$です。

サンプル2
入力
4
17
x 3 67829
x 2 98198
y 2 18912
y 3 67274
x 3 7010
a 1
x 0 9635
a 0
a 3
x 3 5394
a 1
a 4
y 1 3076
a 3
x 1 8612
y 1 55697
a 4
出力
1
1
107834
9636
442357517
731695075
252637976

提出ページヘ