矩阵运算
加减：要求行列数一致，对应位相加减
乘：对于 \(A * B\)，答案 \(ans[i][j]=\sum a[i][k] * b[k][j]\)，要求第一个矩阵列数等于第二个矩阵行数。注意矩阵乘法具有结合律但不具有交换律
矩阵求逆：需要用到行列式，暂咕
矩阵优化递推
最常见的斐波那契有递推式 \(f_i=f _ {i-1}+f _ {i-2}\)
如果只需要知道第 \(n\) 项的值（\(n\) 很大），可以这样做：
定义初始矩阵：
\[A=\begin{bmatrix} f _ {i-2}& f _ {i-1} \end{bmatrix}\]要乘一个转移矩阵 \(B\) 结果为答案矩阵
\[C=\begin{bmatrix} f _ {i-1}& f _ {i} \end{bmatrix}\]那么 \(B\) 可以构造为：
\[\begin{bmatrix} 0&1 \\ 1&1 \end{bmatrix}\]通过定义可以证明这样构造是对的
根据矩阵的结合律，最终要乘 \(n\) 次转移矩阵，不妨先求转移矩阵的 \(n\) 次方然后再乘初始矩阵
而 \(n\) 次方可以快速幂优化
下面采用重载运算符处理矩乘运算
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n;
struct Mat{
int a[2][2];
Mat(){a[0][0]=a[1][0]=a[0][1]=a[1][1]=0;}
};
Mat operator * (Mat b,Mat c){
Mat ans;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++){
ans.a[i][j]=(ans.a[i][j]+b.a[i][k]*c.a[k][j]%mod)%mod;
}
}
}
return ans;
}
Mat po(Mat a,int b){
Mat ans;
ans.a[0][0]=ans.a[1][1]=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
signed main(){
cin>>n;
if(n==1||n==2){
cout<<1;
return 0;
}
Mat c;
c.a[0][1]=c.a[1][0]=c.a[1][1]=1;
Mat p=po(c,n-2);
Mat b;
b.a[0][0]=b.a[0][1]=1;
b=b*p;
cout<<b.a[0][1];
return 0;
}
矩阵优化图上问题
对于图上的 \(dp\)，有限制为与一个点有连边的点才能转移
而如果进行多次这样的操作，可以用矩阵把状态的转移记录下来，用快速幂优化
比如这道题，除了终点一个点可以向相邻点连边，那么表达在矩阵上即为 \((i,i+1)\) 以及 \((i，i-1）\) 的位置为 \(1\)
快速幂后即可知道方案数是多少了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int mod=1000;
const int m=8;
int n;
struct Mat{
int d[10][10];
Mat(){memset(d,0,sizeof d);}
};
Mat operator * (Mat a,Mat b){
Mat ans;
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=m;k++){
ans.d[i][j]+=a.d[i][k]*b.d[k][j]%mod;
}
}
}
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)ans.d[i][j]%=mod;
return ans;
}
Mat po(Mat a,int b){
Mat ans;
for(int i=1;i<=m;i++)ans.d[i][i]=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int main(){
cin>>n;
Mat a;
for(int i=1;i<=m-1;i++){
if(i==4)continue;
a.d[i+1][i]=1;
}
for(int i=2;i<=m;i++){
if(i==6)continue;
a.d[i-1][i]=1;
}
a.d[m][1]=a.d[1][m]=1;
Mat ans=po(a,n);
Mat k;k.d[1][1]=1;
k=k*ans;
cout<<k.d[1][5];
return 0;
}