撰写目录
//盼望着，盼望着，我终于更新了，初赛手感还不错！
众所周知，DP是一个递推的过程，有时最优情况下可以是线性递推。但是如果题目很毒瘤，不仅逼着你推出线性复杂度的递推式，还把\(n\)的取值范围设置成不超过signed long long，那么线性的复杂度也会去世，所以矩阵加速就有了必要。
为了学会矩阵加速，必须要先清楚：
矩阵是什么
在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合，最早来自于方程组的系数及常数所构成的方阵。这一概念由19世纪英国数学家凯利首先提出。
矩阵是高等代数学中的常见工具，也常见于统计分析等应用数学学科中。在物理学中，矩阵于电路学、力学、光学和量子物理中都有应用；计算机科学中，三维动画制作也需要用到矩阵。 矩阵的运算是数值分析领域的重要问题。将矩阵分解为简单矩阵的组合可以在理论和实际应用上简化矩阵的运算。对一些应用广泛而形式特殊的矩阵，例如稀疏矩阵和准对角矩阵，有特定的快速运算算法。关于矩阵相关理论的发展和应用，请参考《矩阵理论》。在天体物理、量子力学等领域，也会出现无穷维的矩阵，是矩阵的一种推广。
——百度百科
矩阵相关的一些定义
1、由\(mxn\)个数\(a_{i,j}\)排成\(m行n列\)的数表成为m行n列的矩阵，简称为\(m*n\)的矩阵。记作：
//图片还是来自百度百科因为我懒得用Latex
2、元：矩阵中的每一个数\(a_{i,j}\)都称为集合\(A\)中的元素，又称为元。
3、元都是实数的矩阵称为实矩阵；元都是复数的矩阵成为复矩阵；行数与列数相等且都为\(n\)的矩阵称为\(n\)阶矩阵。
矩阵的基本运算
加减法
前置要求：只有同型矩阵（即长宽都相等的矩阵）才能进行加法运算
具体做法：直接对位相加（减）
数乘
直接将数乘给矩阵内的每一个元
矩阵乘法
前置条件：矩阵A的列数等于矩阵B的行数
设C为矩阵A与B的积，\(c_{i,j}\)为C中的元
公式: \(c_{i,j}=\sum a_{i,k}*b_{k,j}\)
这个公式乍一看可能很难懂，我们举个例子看一下。
$$
A=
\begin{bmatrix}
a_{1,1} & a_{1,2} & a_{1,3}\\
a_{2,1} & a_{2,2} & a_{2,3}\\
\end{bmatrix}
$$
$$
B=
\begin{bmatrix}
b_{1,1} & b_{1,2}\\
b_{2,1} & b_{2,2}\\
b_{3,1} & b_{3,2}\\
\end{bmatrix}
$$
则有：
$$
C=AB=
\begin{bmatrix}
a_{1,1}b_{1,1}+a_{1,2}b_{2,1}+a_{1,3}b_{3,1} & a_{1,1}b_{1,2}+a_{1,2}b_{2,2}+a_{1,3}b_{3,2} \\
a_{2,1}b_{1,1}+a_{2,2}b_{2,1}+a_{2,3}b_{3,1} & a_{2,1}b_{1,2}+a_{2,2}b_{2,2}+a_{2,3}b_{3,2} \\
\end{bmatrix}
$$
矩阵乘法的性质
1、乘法结合律：\(AB*C=A*BC\)
2、乘法分配律：
\((A+B)*C=AC+BC\)
\(A*(B+C)=AB+AC\)
3、一般不满足交换律，只有一下几种情况下满足交换律：
- 两个矩阵中有至少一个数量矩阵（从左上到右下的对角线上是同一个非0的数，其余元全为0的矩阵
- 两个矩阵相等
- 两个矩阵中有至少一个为0矩阵
- 两矩阵满足AB = A+B
4、如上面的例子一样：一个\(m*p\)的矩阵与一个\(p*n\)的矩阵相乘，结果为一个\(m*n\)的矩阵
到这里，矩阵运算的基本原理就结束了，还有一些更复杂的我没有写在这里，显然是因为我也不会，一般也用不到。
矩阵快速幂
不懂什么是快速幂？点击这里！
学习算法，从板子做起！！！
模板题目： https://www.luogu.org/problem/P3390
这里就简单的说，得益于矩阵乘法满足结合律，矩阵快速幂和普通的快速幂基本没有任何区别，你需要做的只是将普通的乘法转化成矩阵乘法即可。
为了能让我们便捷地沿用快速幂的写法，通常我的习惯是将矩阵丢进一个结构体里，并对这个结构体重载“*”的运算来实现矩阵乘法。具体的做法，请看下面代码里的注释。
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M=110;
const ll Mod=1e9+7;//模数
ll n,k;
struct Matrix{
ll g[M][M];//存储矩阵
Matrix(){
memset(g,0,sizeof(g));//清零
}
Matrix operator * (const Matrix &y){
Matrix ans;//ans为矩乘后的积
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
ans.g[i][j]=(ans.g[i][j]+g[i][k]*y.g[k][j])%Mod;//按照矩阵乘法的规则进行运算
return ans;
}
}a,res;
ll Read(){//快读
ll x=0;
int f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void KSM(ll x){//快速幂
while(x){
if(x&1) res=res*a;
a=a*a;
x>>=1;
}
}
int main(){
n=Read(),k=Read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a.g[i][j]=Read();
for(int i=1;i<=n;i++)//初始化单位矩阵
res.g[i][i]=1;
KSM(k);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%lld ",res.g[i][j]);
putchar('\n');
}
return 0;
}
到这里矩阵快速幂就介绍完了
矩阵加速
学习算法从模板开始！！！
模版题目： https://www.luogu.org/problem/P1962
做法类似与矩阵快速幂。由观察，矩阵乘法的过程中，是可以实现递推的。对于这道例题，我们都知道斐波那契数列中有\(f[n]=f[n-1]+f[n-2]\)的递推关系，所以我们要思考一下如何安排两个矩阵可以使得他们进行递推
设记录结果的矩阵
$$
A=
\begin{bmatrix}
f[n],f[n-1]
\end{bmatrix}
$$
而我们希望在递推后得到的新矩阵
$$
B=
\begin{bmatrix}
f[n+1],f[n]
\end{bmatrix}
$$
其中\(f[n+1]=f[n]+f[n-1]\)。为了实现这样的加法，我们需要推理出来一个合适的单位矩阵：
不难推出这个矩阵应该是\(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\)
验证一下：
$$
\begin{bmatrix}
f[n],f[n-1]
\end{bmatrix}
*
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}
=
\begin{bmatrix}
f[n]*1+f[n-1]*1,f[n]*1+f[n-1]*0
\end{bmatrix}
=
\begin{bmatrix}
f[n+1],f[n]
\end{bmatrix}
$$
递推成功！！！随后只需要直接快速幂来简化递推就可以了，妙啊。上代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll Mod=1e9+7;
ll n;
struct Matrix{
ll g[3][3];
Matrix(){
memset(g,0,sizeof(g));
}
Matrix operator * (const Matrix &b){
Matrix res;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
res.g[i][j]=(res.g[i][j]+g[i][k]*b.g[k][j])%Mod;
return res;
}
}ans,base;
void KSM(ll x){
while(x){
if(x&1) ans=ans*base;
base=base*base;
x>>=1;
}
}
int main(){
scanf("%lld",&n);
base.g[1][1]=base.g[1][2]=base.g[2][1]=1;
ans.g[1][1]=ans.g[1][2]=1;
if(n<=2) return puts("1")&0;
KSM(n-2);
printf("%lld\n",ans.g[1][1]%Mod);
return 0;
}
因为是从 \(n＞2\) 才有递推的，所以在 \(n=3\) 时才会开始用快速幂，因此快速幂中的次方数是 \(n-2\)
再来一道题巩固一下：https://www.luogu.org/problem/P1939
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Mod=1e9+7;
ll n;
struct Matrix{
ll a[4][4];
Matrix(){
memset(a,0,sizeof(a));
}
Matrix operator * (const Matrix &b){
Matrix ans;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
ans.a[i][j]=(ans.a[i][j]+a[i][k]*b.a[k][j])%Mod;
return ans;
}
};
Matrix KSM(int x){
Matrix res,base;
base.a[1][1]=base.a[1][3]=base.a[2][1]=base.a[3][2]=1;
res.a[1][1]=res.a[2][2]=res.a[3][3]=1;
while(x){
if(x&1) res=res*base;
base=base*base;
x>>=1;
}
return res;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
Matrix ans,base;
scanf("%lld",&n);
if(n<=3){
puts("1");
continue;
}
ans=KSM(n);
printf("%lld\n",ans.a[2][1]);
}
return 0;
}
✌