两矩阵 A * B ，当 A 的行数等于 B 的列数时，A * B 合法，结果如下：
1 #include<stdio.h>
2 #include<string.h>
3 typedef long long ll;
4 const int mod=10000007;
5
6 struct mat{
7 int r,c; //r即row，矩阵行数；c即column，矩阵列数
8 ll m[10][10]; //矩阵
9 void clear(){ //归零函数
10 for(int i=1;i<=r;i++)memset(m[i],0,sizeof(m[i]));
11 }
12 };
13
14 mat MatMul(mat m1,mat m2){ //仅当m1.r==m2.c时可以相乘，相乘时可加模运算
15 mat tmp;
16 tmp.r=m1.r; //计算结果的行数与m1行数相等，列数与m2列数相等
17 tmp.c=m2.c;
18 int i,j,k;
19 for(i=1;i<=tmp.r;i++){
20 for(j=1;j<=tmp.c;j++){
21 ll t=0;
22 for(k=1;k<=m1.c;k++){
23 t=(t+(m1.m[i][k]*m2.m[k][j])%mod)%mod;
24 }
25 tmp.m[i][j]=t;
26 }
27 }
28 return tmp;
29 }
30
31 int main(){
32 int t;
33 while(scanf("%d",&t)!=EOF){
34 mat m[2];
35 for(int i=0;i<=1;i++){
36 scanf("%d%d",&m[i].r,&m[i].c);
37 for(int j=1;j<=m[i].r;j++){
38 for(int k=1;k<=m[i].c;k++){
39 scanf("%lld",&m[i].m[j][k]);
40 }
41 }
42 }
43 mat ans=MatMul(m[0],m[1]);
44 for(int i=1;i<=ans.r;i++){
45 for(int j=1;j<=ans.r;j++){
46 printf("%lld ",ans.m[i][j]);
47 }
48 printf("
");
49 }
50 }
51 return 0;
52 }
在之前的矩阵乘法的基础上，引入快速幂的思想，就得到了矩阵的快速幂算法（MatQP，计算矩阵 a 的 n 次幂）：
经过修改，把矩阵加法、乘法、快速幂全部重载了一下，写了构造函数，其中矩阵快速幂支持0次幂等于单位矩阵：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 typedef long long ll;
5 int mod;
6
7 struct mat{
8 int r,c;
9 ll m[4][4]; //经测试最大开成590*590的 ll 型矩阵
10 mat(){}
11 mat(int r,int c):r(r),c(c){}
12 void clear(){
13 memset(m,0,sizeof(m));
14 }
15
16 mat operator+(mat a)const{
17 mat ans(r,c);
18 for(int i=1;i<=r;i++){
19 for(int j=1;j<=c;j++){
20 ans.m[i][j]=(m[i][j]+a.m[i][j])%mod;
21 }
22 }
23 return ans;
24 }
25
26 mat operator*(mat a)const{
27 mat tmp(r,a.c);
28 int i,j,k;
29 for(i=1;i<=tmp.r;i++){
30 for(j=1;j<=tmp.c;j++){
31 tmp.m[i][j]=0;
32 for(k=1;k<=c;k++){
33 tmp.m[i][j]=(tmp.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;
34 }
35 }
36 }
37 return tmp;
38 }
39
40 mat operator^(int n)const{ //需要时可以用 ll n，注意运算符优先级比较低，多用括号；
41 mat ans(r,r),tmp(r,r);
42 memcpy(tmp.m,m,sizeof(tmp.m));
43 ans.clear();
44 for(int i=1;i<=ans.r;i++){
45 ans.m[i][i]=1;
46 }
47 while(n){
48 if(n&1)ans=ans*tmp;
49 n>>=1;
50 tmp=tmp*tmp;
51 }
52 return ans;
53 }
54
55 void print()const{
56 for(int i=1;i<=r;i++){
57 for(int j=1;j<=c;j++){
58 printf("%lld",m[i][j]);
59 if(j==c)printf("
");
60 else printf(" ");
61 }
62 }
63 }
64
65 };
非结构体封装版：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 typedef long long ll;
5 const int mod=1e9+7;
6
7 struct mat{
8 int r,c;
9 ll m[4][4];
10 mat(){}
11 mat(int r,int c):r(r),c(c){}
12 };
13
14 void clear(mat &a){
15 memset(a.m,0,sizeof(a.m));
16 }
17
18 mat mul(mat a,mat b){
19 mat tmp(a.r,b.c);
20 int i,j,k;
21 for(i=1;i<=tmp.r;i++){
22 for(j=1;j<=tmp.c;j++){
23 tmp.m[i][j]=0;
24 for(k=1;k<=a.c;k++){
25 tmp.m[i][j]=(tmp.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;
26 }
27 }
28 }
29 return tmp;
30 }
31
32 mat QP(mat a,int n){
33 mat ans(a.r,a.r),tmp(a.r,a.r);
34 memcpy(tmp.m,a.m,sizeof(tmp.m));
35 clear(ans);
36 for(int i=1;i<=ans.r;i++){
37 ans.m[i][i]=1;
38 }
39 while(n){
40 if(n&1)ans=mul(ans,tmp);
41 n>>=1;
42 tmp=mul(tmp,tmp);
43 }
44 return ans;
45 }
46
47 void print(mat a){
48 for(int i=1;i<=a.r;++i){
49 for(int j=1;j<=a.c;++j){
50 printf("%lld",a.m[i][j]);
51 if(j==a.c)printf("
");
52 else printf(" ");
53 }
54 }
55 }
56
57 int main(){
58
59 return 0;
60 }
另外，遇到题目需要将矩阵运算的乘法和加法分别改为加法和min/max，只要满足矩阵运算结合律，都是可以改写的，此处循环遍历的下标从 0 开始
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const ll INF = 0x3f3f3f3f3f3f3f3f;
5
6 struct mat{
7 int r,c;
8 ll m[45][45];
9 mat(){}
10 mat(int r,int c):r(r),c(c){}
11 };
12
13 void clear(mat &a){
14 memset(a.m,0x3f,sizeof(a.m));
15 }
16
17 inline ll min(ll a, ll b){return a <= b ? a : b ;}
18
19 mat mul(mat a,mat b){
20 mat tmp(a.r,b.c);
21 clear(tmp);
22 int i,j,k;
23 for(i=0;i<tmp.r;i++){
24 for(j=0;j<tmp.c;j++){
25 for(k=0;k<a.c;k++){
26 tmp.m[i][j]=min(tmp.m[i][j], a.m[i][k] + b.m[k][j]);
27 }
28 }
29 }
30 return tmp;
31 }
32
33 mat QP(mat a,int n){
34 mat ans(a.r,a.r),tmp(a.r,a.r);
35 memcpy(tmp.m,a.m,sizeof(tmp.m));
36 clear(ans);
37 for(int i=0;i<ans.r;i++){
38 ans.m[i][i]=0;
39 }
40 while(n){
41 if(n&1)ans=mul(ans,tmp);
42 n>>=1;
43 tmp=mul(tmp,tmp);
44 }
45 return ans;
46 }
47
48 void print(mat a){
49 for(int i=0;i<a.r;++i){
50 for(int j=0;j<a.c;++j){
51 printf("%lld",a.m[i][j]);
52 if(j==a.c-1)printf("
");
53 else printf(" ");
54 }
55 }
56 }