yukicoder-426

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/426 No.426 往復漸化式] ==

=== Description ===

{{{
#!html
<p>有$n$个$3 \times 3$的矩阵$A_i$和$2 \times 2$的矩阵$B_i$，一开始的值都是单位矩阵。考虑一个三元组数列$a$和二元组数列$b$，定义它们的递推式：<br>
$a_{i+1}=A_i a_{i}$<br>
$b_{i-1} = B_i b_i + \begin{pmatrix} 6i & 6i+1 & 6i+2 \\ 6i+3 & 6i+4 & 6i+5\end{pmatrix} a_i$<br>

初始值$a_0$和$b_n$会在一开始给定。
</p>

<p>现在有$q$个操作，每个操作都是下面$4$种的其中一个：
<ol>
<li>修改$A_i$的值</li>
<li>修改$B_i$的值</li>
<li>询问$a_i$的值，对$10^9+7$取模</li>
<li>询问$b_i$的值，对$10^9+7$取模</li>
</ol>
</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$n$<br>
$a_{0(0)}\ a_{0(1)}\ a_{0(2)}$<br>
$b_{n(0)}\ b_{n(1)}$<br>
$q$<br>
$query_1$<br>
$\vdots$<br>
$query_q$<br>
</p>
<p>$1 \le n \le 10^5, 1 \le q \le 10^4$<br>
$a_0 = \begin{pmatrix} a_{0(0)} && a_{0(1)} && a_{0(2)} \end{pmatrix}^T$<br>
$b_n = \begin{pmatrix} b_{n(0)} && b_{n(1)} \end{pmatrix}^T$<br>
保证$a_0$和$b_n$每个值都是$0$到$100$的整数。
</p>

<p>每种操作对应的格式如下：
<ol>
<li>a i a00 a01 a02 a10 a11 a12 a20 a21 a22</li>
<li>b i b00 b01 b10 b11</li>
<li>ga i</li>
<li>gb i</li>
</ol>
</p>
}}}

=== Output ===

对于每个ga操作，输出$3$个数；对于每个gb操作，输出$2$个数。

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
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
</pre>
}}}
输出
{{{
#!html
<pre>
1 2 3
48 67
6 12 18
268 377
6 12 18
264 381
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
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
</pre>
}}}
输出
{{{
#!html
<pre>
114 63 84
1968040 1994095
1803 1887 522
129291 141932
14875989 12385294
0 5
1803 1887 522
32751948 35923913
</pre>
}}}

No.426 往復漸化式

Description

有$n$个$3 \times 3$的矩阵$A_i$和$2 \times 2$的矩阵$B_i$，一开始的值都是单位矩阵。考虑一个三元组数列$a$和二元组数列$b$，定义它们的递推式：
$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$会在一开始给定。

现在有$q$个操作，每个操作都是下面$4$种的其中一个：

修改$A_i$的值
修改$B_i$的值
询问$a_i$的值，对$10^9+7$取模
询问$b_i$的值，对$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 \le n \le 10^5, 1 \le q \le 10^4$
$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$和$b_n$每个值都是$0$到$100$的整数。

每种操作对应的格式如下：

a i a00 a01 a02 a10 a11 a12 a20 a21 a22
b i b00 b01 b10 b11
ga i
gb i

Output

对于每个ga操作，输出$3$个数；对于每个gb操作，输出$2$个数。

Sample

Sample 1

输入

11 2 34 58ga 1gb 0a 0 1 1 1 2 2 2 3 3 3ga 1gb 0b 1 0 0 1 1ga 1gb 0

输出

1 2 348 676 12 18268 3776 12 18264 381

Sample 2

输入

56 5 80 519a 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 2b 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 1b 4 6 2 9 6 ga 5gb 4gb 0gb 5a 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 3gb 4

输出

114 63 841968040 19940951803 1887 522129291 14193214875989 123852940 51803 1887 52232751948 35923913