問題一覧 > 通常問題

No.426 往復漸化式

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : はむこはむこ / テスター : りあんりあん
1 ProblemId : 1321 / 出題時の順位表
問題文最終更新日: 2016-09-23 15:15:05

問題文

$3 \times 3$行列$A_i (0 \leq i < n)$, $2 \times 2$行列$B_i (0 < i \leq n)$がある。初期値は全て単位行列である。
$3$次元ベクトル列$a_i (0 \leq i \leq n)$, $2$次元ベクトル列$b_i (0 \leq i \leq n)$は、以下のように定義される。

$a_{i+1} = A_i a_i$
$b_{i-1} = B_i b_i + \begin{pmatrix} 6i & 6i+1 & 6i+2 \\ 6i+3 & 6i+4 & 6i+5\end{pmatrix} a_i$

漸化式の初期値として$a_0, b_n$が与えられる。

4種類のクエリタイプ、クエリa, クエリb, クエリga, クエリgbがある。これらのクエリを$q$個処理せよ。
(1) クエリa i
$A_i$を変更する。
(2) クエリb i
$B_i$を変更する。
(3) 取得クエリga i
$a_i$の各要素を、それぞれ$10^9+7$で割ったあまりを出力する。
(4) 取得クエリgb i
$b_i$の各要素を、それぞれ$10^9+7$で割ったあまりを出力する。

入力

$n$
$a_{0(0)}\ a_{0(1)}\ a_{0(2)}$
$b_{n(0)}\ b_{n(1)}$
$q$
$query_1$
$\vdots$
$query_q$

$1 \leq n \leq 100000$
$1 \leq q \leq 10000$
$a_0 = \begin{pmatrix} a_{0(0)} && a_{0(1)} && a_{0(2)} \end{pmatrix}^T$
$b_n = \begin{pmatrix} b_{n(0)} && b_{n(1)} \end{pmatrix}^T$
$a_0$の要素は$0$以上$100$未満の整数
$b_n$の要素は$0$以上$100$未満の整数
少なくとも1つのクエリgaもしくはクエリgbが存在する。

クエリa
形式

a i a00 a01 a02 a10 a11 a12 a20 a21 a22 
$A_i = \begin{pmatrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \end{pmatrix} $に変更する。
$0 \leq i < n$
$A_i$の要素は$0$以上$100$未満の整数

クエリb
形式
b i b00 b01 b10 b11
$B_i = \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11}\end{pmatrix}$に変更する。
$0 < i \leq n$
$B_i$の要素は$0$以上$100$未満の整数

クエリga, gb
形式
ga i
gb i
$0 \leq i \leq n$

出力

クエリga
形式

a0 a1 a2
クエリgb
形式
b0 b1

サンプル

サンプル1
入力
1
1 2 3
4 5
8
ga 1
gb 0
a 0 1 1 1 2 2 2 3 3 3
ga 1
gb 0
b 1 0 0 1 1
ga 1
gb 0
出力
1 2 3
48 67
6 12 18
268 377
6 12 18
264 381

始めの2つのga, gbクエリでは、$A_0, B_1$は単位行列なので、
$a_1 = A_0 a_0 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\2 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\2 \\ 3 \end{pmatrix}$
$b_0 = B_1 b_1 + \begin{pmatrix} 6&7&8\\9&10&11 \end{pmatrix} a_1= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 4 \\ 5\end{pmatrix} + \begin{pmatrix} 6&7&8\\9&10&11 \end{pmatrix} \begin{pmatrix} 1 \\2 \\ 3 \end{pmatrix} = \begin{pmatrix} 48 \\ 67 \end{pmatrix}$
次の2つのga, gbクエリでは、$A_0$が変更されているので、
$a_1 = A_0 a_0 = \begin{pmatrix} 1 &1 &1\\ 2 &2 &2\\ 3 &3 &3\end{pmatrix} \begin{pmatrix} 1 \\2 \\ 3 \end{pmatrix} = \begin{pmatrix} 6\\12\\18 \end{pmatrix}$
$b_0 = B_1 b_1 + \begin{pmatrix} 6&7&8\\9&10&11 \end{pmatrix} a_1= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 4 \\ 5\end{pmatrix} + \begin{pmatrix} 6&7&8\\9&10&11 \end{pmatrix} \begin{pmatrix}6\\12\\18 \end{pmatrix} = \begin{pmatrix} 268 \\377 \end{pmatrix}$
次の2つのga, gbクエリでは、$B_1$が変更されているので、
$a_1 = A_0 a_0 = \begin{pmatrix} 1 &1 &1\\ 2 &2 &2\\ 3 &3 &3\end{pmatrix} \begin{pmatrix} 1 \\2 \\ 3 \end{pmatrix} = \begin{pmatrix} 6\\12\\18 \end{pmatrix}$
$b_0 = B_1 b_1 + \begin{pmatrix} 6&7&8\\9&10&11 \end{pmatrix} a_1= \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 4 \\ 5\end{pmatrix} + \begin{pmatrix} 6&7&8\\9&10&11 \end{pmatrix} \begin{pmatrix} 6\\ 12\\ 18 \end{pmatrix} = \begin{pmatrix}264 \\381 \end{pmatrix}$

サンプル2
入力
5
6 5 8
0 5
19
a 2 2 2 5 5 5 1 2 5 1 
a 0 5 4 8 1 5 4 5 6 3 
b 4 5 8 5 8 
ga 2
b 1 3 5 1 5 
a 2 5 2 8 4 8 9 8 9 5 
a 2 9 3 7 9 3 8 2 2 2 
gb 1
b 4 6 2 9 6 
ga 5
gb 4
gb 0
gb 5
a 3 9 9 1 4 6 1 1 5 4 
b 2 3 8 6 7 
b 4 4 7 7 7 
a 4 6 5 8 1 7 8 3 9 8 
ga 3
gb 4
出力
114 63 84
1968040 1994095
1803 1887 522
129291 141932
14875989 12385294
0 5
1803 1887 522
32751948 35923913

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。