矩阵加法：
C~ij~ = A~ij~ + B~ij~ 。
矩阵数乘：
将该数与每一个元素相乘。
矩阵乘法：
设A大小为n * m，B大小为m * p。则A和B的乘积得到的矩阵大小为n * p。
其中每一项 (AB)~ij~ = \(\sum_{k=1}^m\) A~ik~B~kj~ 。
矩阵乘法不满足交换律
矩阵乘法满足结合律和分配律
单位矩阵：
A~ii~ = 1，即左上到右下的对角线都为1，此时任何矩阵乘以单位举证就是它本身。
矩阵快速幂：
快速求矩阵A的N次方。
由于矩阵符合乘法分配律，所以与正常快速幂同理，A^n^ = A^n/2^ * A^n/2^，
\(PS\)：正常快速幂中的累乘器的初始值为单位矩阵，A^1^为所给矩阵。
Luogu P3390，矩阵快速幂模板
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 105
int n;
struct mat{
ll a[maxn][maxn];
mat (){memset(a,0,sizeof(a));}
inline void build(){for(int i = 1;i<=n;++i)a[i][i] = 1;}
}a;
mat operator * (const mat &x,const mat &y){
mat z;
for(int k = 1;k<=n;++k)
for(int i = 1;i<=n;++i)
for(int j = 1;j<=n;++j)
z.a[i][j] = (z.a[i][j] + x.a[i][k]*y.a[k][j]%mod)%mod;
return z;
}
ll k;
inline void init(){
cin>>n>>k;
for(int i = 1;i<=n;++i)
for(int j = 1;j<=n;++j)
cin>>a.a[i][j];
}
int main(){
init();
mat ans;
ans.build();
do{
if(k&1)ans = ans*a;
a = a*a;
k >>= 1;
}
while(k);
for(int i = 1;i<=n;putchar('\n'),++i)
for(int j = 1;j<=n;++j)
cout<<ans.a[i][j]<<" ";
return 0;
}
矩阵加速数列：
我来讲一下学习心得吧。
$ e.g$ $，a[x] = a[x-1] + a[x-3] (x > 3)，a[1] = a[2] = a[3] = 1 $ ，用矩阵加速递推
\(： PS：\) 注意看清普通矩阵递推和普通递推。
首先，普通矩阵递推和普通递推是等效的，而因为矩阵可以快速幂进行加速，所以构造矩阵用矩阵快速幂加速普通矩阵递推。
对于这一题，我们发现对下次或今后递推有用的变量按顺序构成的矩阵是这样的：
以下矩阵中a[]表示的是一个值。
\[ \left[\begin{matrix}a[x-1]\\a[x-2]\\a[x-3]\end{matrix}\right]\]那么我们普通矩阵递推，求的就是a[x]。根据题目,\(a[x] = a[x-1]+a[x-3]\)。
所以我们递推下去就得到了 \[ \left[\begin{matrix}a[x-1]+a[x-3] = a[x]\\a[x-1]\\a[x-2]\\a[x-3]\end{matrix}\right]\]，显然我们要求a[x]。
但是a[x-3]对今后的递推已经无用了！我们就把它删掉，就有了\[ \left[\begin{matrix}a[x]\\a[x-1]\\a[x-2]\end{matrix}\right]\]。
那么我们就需要构造另外一个矩阵A，使得\[ A * \left[\begin{matrix}a[x-1]\\a[x-2]\\a[x-3]\end{matrix}\right] = \left[\begin{matrix}a[x]\\a[x-1]\\a[x-2]\end{matrix}\right]\]。
因为\(a[x] = a[x-1] * 1+a[x-3] * 1\)，所以得到A矩阵第一行为1,0,1（根据矩阵乘法）
因为我们当前已经把a[x-1]和a[x-2]算出来了！所以A矩阵的第二行为1,0,0，第三行为0,1,0。
所以有\[ A = \left[\begin{matrix}1&0&1\\1&0&0\\0&1&0\end{matrix}\right] \]
\(：PS：\)随着题目的变化，这个系数可以不为1或0.
所以,由于每一个矩阵乘以A都能得到下一个矩阵，那么我们将初始矩阵\(a[1] = a[2] = a[3] = 1\)乘以A的N-3次方就能得到第N+1个矩阵（根据矩阵乘法结合律，我们可以先快速幂算A^N-3^）。
注意，这里的初始矩阵a[1] = a[2] = a[3] = 1,乘任何矩阵等于它本身，所以可以忽略。
为什么是N-3次方？因为a[1],a[2],a[3]已经给出a[1],a[2],a[3]已经给出，相当于初始矩阵是第三个矩阵，准备求第四个矩阵，而第四个矩阵的第一项是a[N+1]，所以我们只要输出第四个矩阵的第二行第一个。（根据我们对A的定义，此时A[ 2 ] [ 1 ]表示a[x-1]*1）
Luogu P1939，矩阵加速数列模板
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
#define ll long long
int T,n;
struct mat{
ll m[5][5];
}ans,t;
void init(){
memset(ans.m,0,sizeof(ans.m));
for(int i = 1;i<=3;++i)ans.m[i][i] = 1;
memset(t.m,0,sizeof(t.m));
t.m[1][1] = t.m[1][3] = t.m[2][1] = t.m[3][2] = 1;
}
mat mul(mat a,mat b){
mat res;
memset(res.m,0,sizeof(res.m));
for(int i = 1;i<=3;++i)
for(int j = 1;j<=3;++j)
for(int k = 1;k<=3;++k)
res.m[i][j] += (a.m[i][k]%mod)*(b.m[k][j]%mod),
res.m[i][j] %= mod;
return res;
}
void qmpow(int p){
while(p){
if(p&1)ans = mul(ans,t);
p>>=1;
t = mul(t,t);
}
}
int main(){
cin>>T;
while(T--){
cin>>n;
if(n <= 3)cout<<1<<endl;
else{
init();
qmpow(n);
cout<<ans.m[2][1]<<endl;
}
}
}
总结：分析题目，构造初始有效矩阵，推出接下来的矩阵，再根据矩阵乘法构造A矩阵，对A矩阵进行快速幂，求得目标矩阵。
矩阵求逆
CSP不考？咕咕
