No.426 往復漸化式
はむこ
りあん問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。