# 矩阵乘法总结

Contents

\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}\\
\end{bmatrix}

$$(AB)_{ij}=\sum_{k=1}^p a_{ik} b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{ip}b_{pj}$$

luogu3390

$$f[i]=f[i-1]+f[i-2],f[0]=0,f[1]=1$$

\begin{align*}
A=\begin{bmatrix}
f_i\\
f_{i+1}\\
\end{bmatrix}
B=\begin{bmatrix}
f_{i+1}\\
f_{i+2}\\
\end{bmatrix}
\end{align*}

\begin{bmatrix}
a & b\\
c & d\\
\end{bmatrix}

\begin{align*}
\begin{bmatrix}
f_i\\
f_{i+1}\\
\end{bmatrix}
\times \begin{bmatrix}
a & b\\
c & d\\
\end{bmatrix}
=\begin{bmatrix}
f_{i+1}\\
f_{i+2}\\
\end{bmatrix}
\end{align*}

\begin{align*}
\left\{
\begin{aligned}
f_i \times a + f_{i+1} \times b = f_{i+1} \\
f_i \times c + f_{i+1} \times d = f_{i+2} \\
\end{aligned}
\right.
\end{align*}

\begin{bmatrix}
a=0 & b=1\\
c=1 & d=1\\
\end{bmatrix}

$$f_n=8f_{n-3}+3f_{n-2}+f_{n-1}+n^2+n+8$$

\begin{align*}
\begin{bmatrix}
f_{n-3}\\
f_{n-2}\\
f_{n-1}\\
n^2\\
n\\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
f_{n-2}\\
f_{n-1}\\
f_{n}\\
(n+1)^2\\
n+1\\
\end{bmatrix}
\end{align*}

\begin{align*}
\begin{bmatrix}
f_{n-1}\\
f_{n-2}\\
f_{n-3}\\
n^2\\
2n\\
1\\
n\\
1\\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
f_{n}\\
f_{n-1}\\
f_{n-2}\\
(n+1)^2\\
2(n+1)\\
1\\
n+1\\
1\\
\end{bmatrix}
\end{align*}

\begin{matrix}
& f_{n} & f_{n-1} & f_{n-2} & (n+1)^2 & 2(n+1) & 1 & n+1 & 1\\
f_{n-1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
f_{n-2} & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
f_{n-3} & 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
n^2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
2n & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0\\
n & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
1 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 1\\
\end{matrix}

\begin{matrix}
& f_{n} & f_{n-1} & f_{n-2} & (n+1)^2 & 2(n+1) & 1 & n+1 & 1 & 8\\
f_{n-1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
f_{n-2} & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
f_{n-3} & 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
n^2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
2n & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\
n & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 1 & 0\\
8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{matrix}

### 描述

$$f(x)=a \times f(x-2)+b \times f(x-1)+c$$

### 样例输入

2
1 1 1 1 0 5
1 1 -1 -10 -100 3

### 样例输出

5
999896

\begin{matrix}
& f_{n} & f_{n-1} & 1\\
f_{n-1} & b & 1 & 0\\
f_{n-2} & a & 0 & 0\\
1 & 1 & 0 & 1\\
\end{matrix}