题解：P10503 233 Matrix
_Liyx_
·
·
题解
矩阵快速幂
这里用 a_{i,j} 来表示 233 矩阵第 i 行，第 j 列的数字。
可以使用瞪眼法看出：第 j-1 列可以推出第 j 列。
a_{0,j}=a_{0,j-1} \times 10+3
对于1 \le i \le n来说，a_{i,j}=a_{i-1,j}+a_{i,j-1}。
我们有矩阵：
3 & a_{0,i} & a_{1,i} & a_{2,i} & \cdots & a_{n,i}
\end{bmatrix}
（ 3 是为了让上文中 a_{0,j}=a_{0,j-1} \times 10+3 的 3 可以加上）
而我们要让 F_{i-1}\times K=F_i，如果我们能推出矩阵 K 那这道题就解决了。
（这不是显然吗）
先看 F_0，F_0=\begin{bmatrix}
3 & 23 & a_{1,0} & a_{2,0} & \cdots & a_{n,0}
\end{bmatrix}
矩阵前两列分别为 \begin{pmatrix}
1
\\0
\\0
\\0
\\\vdots
\\0
\end{pmatrix} 和 \begin{pmatrix}
1
\\10
\\0
\\0
\\\vdots
\\0
\end{pmatrix}。
因为 a_{i,j}=a_{i-1,j}+a_{i,j-1}，所以第 k 列（3\le k \le n+2）前 k 项与第 k-1 列的前 k-1 项相同，第 k 项为1。下面放一下矩阵 K。
1 & 1 & 1 & 1 & \cdots & 1\\
0 & 10 & 10 & 10 & \cdots & 10\\
0 & 0 & 1 & 1 & \cdots & 1\\
0 & 0 & 0 & 1 & \cdots & 1\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & 0 & \cdots & 1
\end{bmatrix}
最后用 F_0 \times K^m 得到的矩阵第 1 行最后一个数即为所求。
Code
https://www.luogu.com.cn/paste/hcbvaiw0