矩阵加速数列
矩阵乘法
没错,就是讲一下这么简单的东西,但是大家可要注意:
“别看矩阵乘法简单,矩阵可不简单 (逃”
并且luogu的题解有点错误,导致许多初学者混淆不清,我有必要出面写个模板题题解
了解一下矩阵乘法的定义:
如果 A,B是矩阵,A的大小为 \(n*m\) , B的大小为 \(m*r\)
\[如果C=A*B 那么对于C中的每个元素C_{i,j}就有:\]
\[C_{i,j}=\sum_{k=1}^m A_{i,k}*B_{k,j}\]
所以C的大小为\(n*r\),所以我们发现 只有A矩阵的列=B矩阵的行数 它们才能进行矩阵乘法。所以在矩阵乘法里不一定满***换率,也就是 \(A*B\) ≠ \(B*A\),甚至说如果可以 \(A*B\),但是 \(B*A\) 不一定合法。
洛谷P1939 矩阵加速模板
如果有矩阵快速幂基础就简单了。
设 F = []
(糟了,不会Latex...)