矩阵构建
一个$m$行$n$列（记为$m\times n$）的矩阵用二维数组$matrix$存储，$matrix_{i,j}$表示第$i$行第$j$列元素的值。
在学习矩阵快速幂之前，你需要先学习快速幂
结构体式构建
矩阵构建
一个$m$行$n$列（记为$m\times n$）的矩阵用二维数组$matrix$存储，$matrix_{i,j}$表示第$i$行第$j$列元素的值。
结构体式构建
struct matrix{
ll m[101][101];
int c,r;
matrix(){
memset(m,0,sizeof(m));
c=0,r=0;
}
void matrix_read(){
for(int i=1;i<=c;i++)
for(int j=1;j<=r;j++)
read(m[i][j]);
return;
}
void matrix_print(){
for(int i=1;i<=c;i++){
for(int j=1;j<=r;j++){
print(m[i][j]);
space;
}
enter;
}
return;
}
}矩阵加减法
矩阵加减法比较简单，把两个矩阵对应的位置元素相加减即可。要求两个矩阵的行数和列数是完全相同的。
矩阵的乘法
代数式与矩阵相乘
首先规定矩阵$\mathbf{A}=\begin{bmatrix} a & b \\ c & d \\ e & f \end{bmatrix}$
一个代数式，用$k$来表示，那么$k$成矩阵$\mathbf{A}$就可以记为$k\mathbf{A}$。计算时只需要将矩阵中的每个数乘上$k$。用式子表示为
$$k\mathbf{A}=\begin{bmatrix} ka & kb \\ kc & kd \\ ke & kf \end{bmatrix}$$
矩阵与矩阵相乘
规定矩阵$\mathbf{B}=\begin{bmatrix} g & h & i \\ j & k & l \end{bmatrix}$
$\mathbf{A}$乘$\mathbf{B}$要求$\mathbf{A}$的列数与$\mathbf{B}$的行数相同，计算$\mathbf{A}\times \mathbf{B}$的公式为
$$(\mathbf{A} \times \mathbf{B})_{i,j} = \sum^n_{k=1} \mathbf{A}_{i,k} + \mathbf{B}_{k,j}$$
用例式表示为：
$\mathbf{A}\times \mathbf{B}=\begin{bmatrix} ag+bj & ah+bk & ai+bl \\ cg+cj & ch +ck & ci+dl \\ eg+fj & eh+fk & ei+fl \end{bmatrix}$
代码
普通版
for(int i=1;i<=m;i++)
for(int j=1;j<=u;j++)
for(int k=1;k<=n;k++)
c[i][j]+=a[i][k]*b[k][j];重载运算符版
matrix operator *(const matrix &x,const matrix &y){
matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]+x.m[i][k]*y.m[k][j])%mod;
return c;
}矩阵快速幂
在学习矩阵快速幂之前，你需要先学习快速幂
如果矩阵的行数与列数完全相同，那么它就可以自乘，把$n$个$\mathbf{A}$相乘记为$\mathbf{A}^n$。同样地，矩阵可以进行快速幂计算，与普通的快速幂原理几乎一致。
代码
Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
ll n,K,mod=inf+7;
struct matrix{
ll m[101][101];
matrix(){
memset(m,0,sizeof(m));
}
void matrix_read(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
read(m[i][j]);
return;
}
void matrix_print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
print(m[i][j]);
space;
}
enter;
}
return;
}
}a,ans;
matrix operator *(const matrix &x,const matrix &y){
matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]+x.m[i][k]*y.m[k][j])%mod;
return c;
}
matrix matrix_pow(matrix x,ll num){
matrix pow_ans;
memset(pow_ans.m,0,sizeof(pow_ans.m));
for(int i=1;i<=n;i++) pow_ans.m[i][i]=1;
while(num){
if(num&1) pow_ans=pow_ans*x;
x=x*x;
num>>=1;
}
return pow_ans;
}
int main(){
read(n,K);
a.matrix_read();
ans=matrix_pow(a,K);
ans.matrix_print();
return 0;
}矩阵快速幂加速递推
有一类题目是求线性递推数列的值。例如斐波那契数列，直接计算会超时，一般采用矩阵快速幂加速递推的值。
代码
来源：洛谷：P1939 【模板】矩阵加速（数列）
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
LL n,mod=1e9+7,t;
struct Node{
LL a[4][4];
Node(){
memset(a,0,sizeof(a));
}
Node operator * (const Node p)const{
Node res;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
res.a[i][j]=(res.a[i][j]+a[i][k]*p.a[k][j])%mod;
return res;
}
}Base,ans;
void ksm(Node x,LL p){
while(p){
if(p&1)
Base=Base*x;
x=x*x;
p>>=1;
}
}
int main(){
read(t);
while(t--){
read(n);
if(n<=3){
print(1);
enter;
continue;
}
ans.a[1][1]=ans.a[1][2]=ans.a[2][3]=ans.a[3][1]=1;
Base.a[1][1]=Base.a[1][2]=Base.a[1][3]=1;
ksm(ans,n-3);
print(Base.a[1][1]);
enter;
}
return 0;
}struct matrix{
ll m[101][101];
int c,r;
matrix(){
memset(m,0,sizeof(m));
c=0,r=0;
}
void matrix_read(){
for(int i=1;i<=c;i++)
for(int j=1;j<=r;j++)
read(m[i][j]);
return;
}
void matrix_print(){
for(int i=1;i<=c;i++){
for(int j=1;j<=r;j++){
print(m[i][j]);
space;
}
enter;
}
return;
}
}普通版
for(int i=1;i<=m;i++)
for(int j=1;j<=u;j++)
for(int k=1;k<=n;k++)
c[i][j]+=a[i][k]*b[k][j];重载运算符版
matrix operator *(const matrix &x,const matrix &y){
matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]+x.m[i][k]*y.m[k][j])%mod;
return c;
}矩阵快速幂
在学习矩阵快速幂之前，你需要先学习快速幂
代码
Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
ll n,K,mod=inf+7;
struct matrix{
ll m[101][101];
matrix(){
memset(m,0,sizeof(m));
}
void matrix_read(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
read(m[i][j]);
return;
}
void matrix_print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
print(m[i][j]);
space;
}
enter;
}
return;
}
}a,ans;
matrix operator *(const matrix &x,const matrix &y){
matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.m[i][j]=(c.m[i][j]+x.m[i][k]*y.m[k][j])%mod;
return c;
}
matrix matrix_pow(matrix x,ll num){
matrix pow_ans;
memset(pow_ans.m,0,sizeof(pow_ans.m));
for(int i=1;i<=n;i++) pow_ans.m[i][i]=1;
while(num){
if(num&1) pow_ans=pow_ans*x;
x=x*x;
num>>=1;
}
return pow_ans;
}
int main(){
read(n,K);
a.matrix_read();
ans=matrix_pow(a,K);
ans.matrix_print();
return 0;
}矩阵快速幂加速递推
有一类题目是求线性递推数列的值。例如斐波那契数列，直接计算会超时，一般采用矩阵快速幂加速递推的值。
代码
来源：洛谷：P1939 【模板】矩阵加速（数列）
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
LL n,mod=1e9+7,t;
struct Node{
LL a[4][4];
Node(){
memset(a,0,sizeof(a));
}
Node operator * (const Node p)const{
Node res;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
res.a[i][j]=(res.a[i][j]+a[i][k]*p.a[k][j])%mod;
return res;
}
}Base,ans;
void ksm(Node x,LL p){
while(p){
if(p&1)
Base=Base*x;
x=x*x;
p>>=1;
}
}
int main(){
read(t);
while(t--){
read(n);
if(n<=3){
print(1);
enter;
continue;
}
ans.a[1][1]=ans.a[1][2]=ans.a[2][3]=ans.a[3][1]=1;
Base.a[1][1]=Base.a[1][2]=Base.a[1][3]=1;
ksm(ans,n-3);
print(Base.a[1][1]);
enter;
}
return 0;
}
