No.426 Round-Trip Recurrence
はむこ
りあんProblem Statement
There are $3 \times 3$ matrices $A_i (0 \leq i < n)$ and $2 \times 2$ matrices $B_i (0 < i \leq n)$. Initially, all of them are identity matrices.
The sequence of $3$-dimensional vectors $a_i (0 \leq i \leq n)$ and the sequence of $2$-dimensional vectors $b_i (0 \leq i \leq n)$ are defined as follows.
$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$ are given as the initial values of the recurrences.
There are 4 types of queries: query a, query b, query ga, query gb. Process $q$ of these queries.
(1) Query a i
Modify $A_i$.
(2) Query b i
Modify $B_i$.
(3) Retrieval query ga i
Output each element of $a_i$ modulo $10^9+7$.
(4) Retrieval query gb i
Output each element of $b_i$ modulo $10^9+7$.
Input
$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$
The elements of $a_0$ are integers at least $0$ and less than $100$.
The elements of $b_n$ are integers at least $0$ and less than $100$.
There is at least 1 query ga or query gb.
Query a
Format
a i a00 a01 a02 a10 a11 a12 a20 a21 a22Change to $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$
The elements of $A_i$ are integers at least $0$ and less than $100$.
Query b
Format
b i b00 b01 b10 b11Change to $B_i = \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11}\end{pmatrix}$.
$0 < i \leq n$
The elements of $B_i$ are integers at least $0$ and less than $100$.
Queries ga, gb
Format
ga i gb i$0 \leq i \leq n$
Output
Query ga
Format
a0 a1 a2Query gb
Format
b0 b1
Sample
Sample 1
Input
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
Output
1 2 3 48 67 6 12 18 268 377 6 12 18 264 381
In the first two queries ga, gb, since $A_0, B_1$ are identity matrices,
$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}$
In the next two queries ga, gb, since $A_0$ has been changed,
$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}$
In the next two queries ga, gb, since $B_1$ has been changed,
$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}$
Sample 2
Input
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
Output
114 63 84 1968040 1994095 1803 1887 522 129291 141932 14875989 12385294 0 5 1803 1887 522 32751948 35923913
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。