1.快速入门
洛谷B2105 矩阵乘法，看到题目，题目中已经告诉了我们矩阵乘法的基本操作，按照题目模拟即可
给出我的代码：
#include <bits/stdc++.h>
using namespace std;
int x[105][105];
int y[105][105];
int main(){
int n,m,k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> x[i][j];
for (int i = 1; i <= m; i++) for (int j = 1; j <= k; j++) cin >> y[i][j];
for (int i = 1; i <= n; i++){
for (int j = 1; j<= k; j++){
int z = 0;
for (int k = 1; k <= m; k++){//套公式
z += x[i][k]*y[k][j];
}
cout << z << " ";
}
cout << "\\n";
}
return 0;
}
z我咋没用数组存
2.矩阵快速幂
P3390 【模板】矩阵快速幂
还记得那个矩阵乘法的模板吗？只需将它套入快速幂的模板里即可。
但是这边细节比较多，本蒟蒻也不太会用类，给出一个比较浅显的代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int The_Boeing_757_is_the_best_aircraft_model_in_the_world = 1e9+7;
int n;
int x[104][104];
int a[104][104];
int y[104][104];
int z[104][104];
void m(){
memset(z,0,sizeof(z));
for (int i = 1; i <= n; i++){
for (int j = 1; j<= n; j++){
for (int k = 1; k <= n; k++){//套公式
(z[i][j] += x[i][k]*y[k][j]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
}
}
}
}
void boeing(){//转换函数
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) x[i][j] = z[i][j];
}
}
void airbus(){//转换函数
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) y[i][j] = z[i][j];
}
}
void fast(int k){//统一把这一次的乘积放x，方便之后处理
if (k == 0){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) x[i][j] = 0;
x[i][i] = 1;
}
return ;
}
if (k == 1){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) x[i][j] = a[i][j];
}
return ;
}
fast(k/2);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) y[i][j] = x[i][j];
m();
airbus();
fast(k%2);
m();
boeing();
}
signed main(){
int k;
cin >> n >> k;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> a[i][j];
a[i][j] %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
}
}
fast(k);
for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++) {cout << x[i][j] << " ";} cout << "\\n";}
return 0;
}
不要管我的变量名和函数名啊
总体而言，在细节处理时：我将每一次的结果存在x里，这样方便统计。
举个例子：
我们在计算矩阵的k次方。
先调用函数算出
k/2
次方的矩阵，存在x里。
复制一份，放到y里
用m函数计算出x*y的值——也就是矩阵的k/2*k/2次方，存放到z里
当然如果k是奇数，那么还要再乘一遍
统一再乘一遍
那么将z中的转移到y
然后调用fast(k%2)
再（用m函数）乘
再将z中的转移到x里存放
感觉总体还是比较简单的，至少跟用类的对比
这样的模板就写好了，思路不难，就是细节有点多
3.简单的优化
那么好问题，我们学了矩阵乘法该怎么用呢？
请看入门题目——P1962 斐波那契数列 – 洛谷
对于60%的数据用普通DP即可，以下是转移方程：
dp[i] = dp[i-1]+dp[i-2]
只看60%的数据，实现就是个普及-，可是当n<
时，O(n)的时间复杂度不再能支撑
此时就要用到矩阵乘法优化了！
如何构建？ 1.写出递推： 此题为：f[n] = f[n-1]+f[n-2] 2.构建矩阵 先放dp[i]、再看dp[i]要哪些转移过来、再看dp[i]要哪些转移过来的要要哪些转移过来… 此题为： dp[i] dp[i-1] 3.考虑次方矩阵 转移为dp[i]从以的dp[i-1]为第一项的转来 为了方便描述，以的dp[i]为第一项称为A（矩阵）,以的dp[i-1]为第一项称为B（矩阵） 对于次方矩阵C（叫做C）第i行代表A[i] = ∑[在列j] B[j] * C[i][j] 靠递推转移方程进行构建C，以及对于入门\\正常的矩阵乘法优化A与B一般是一列，所以在我的表达式里A[i][1]=>(写为)A[i],其他同理 此题为： 1 1（dp[i] = dp[i-1]*1+dp[i-2]*1） 1 0（dp[i-1] = dp[i-1]*1+dp[i-2]*0）
注意再乘 确定的前几项 即可：
代码是在模板上稍加修改的：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int The_Boeing_757_is_the_best_aircraft_model_in_the_world = 1e9+7;
int n;
int x[104][104];
int a[104][104];
int y[104][104];
int z[104][104];
void m(){
memset(z,0,sizeof(z));
for (int i = 1; i <= n; i++) for (int j = 1; j<= n; j++) for (int k = 1; k <= n; k++)(z[i][j] += x[i][k]*y[k][j]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
}
void boeing(){ for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) x[i][j] = z[i][j];}
void airbus(){for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) y[i][j] = z[i][j];}
void fast(int k){//统一把这一次的乘积放x，方便之后处理
if (k == 0){
for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){ x[i][j] = 0;}x[i][i] = 1;}
return ;
}
if (k == 1){
for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++) x[i][j] = a[i][j];}
return ;
}
fast(k/2);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) y[i][j] = x[i][j];
m();
airbus();
fast(k%2);
m();
boeing();
}
signed main(){
int k;
cin >> k;
if (k < 2){ cout << 1;return 0;}
n = 2;
a[1][1] = 1;
a[1][2] = 1;
a[2][1] = 1;
fast(k-2);//我们以第三项来举例:第三项只是*了一次就可以得到,所以是N减二
memset(y,0,sizeof y);
y[1][1] = 1;
y[2][1] = 1;
int ans = 0;
for (int k = 1; k <= 2; k++) (ans += x[1][k]*y[k][1]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
cout << ans;
return 0;
}
4.习题
P1939 矩阵加速（数列） – 洛谷
P1349 广义斐波那契数列 – 洛谷
都是比较简单的思路，与P1962 斐波那契数列思路都差不多
以下是我的解题思路：
P1939:
状态： dp[i] dp[i-1] dp[i-2] 想求dp[i]就要从第一位为dp[i-1]更新来 记住！a*b是用a的一行*b的一列 轻松得出： 1(让第一位0 +dp[i-1]) 0 1(让第一位0+dp[i-1] +dp[i-3]) 1(让第2位0 +dp[i-1]) 0 0 0 1(让第3位0 +dp[i-2]) 0
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int The_Boeing_757_is_the_best_aircraft_model_in_the_world = 1e9+7;
int n;
int x[104][104];
int a[104][104];
int y[104][104];
int z[104][104];
void m(){
memset(z,0,sizeof(z));
for (int i = 1; i <= n; i++) for (int j = 1; j<= n; j++) for (int k = 1; k <= n; k++)(z[i][j] += x[i][k]*y[k][j]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
}
void boeing(){ for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) x[i][j] = z[i][j];}
void airbus(){for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) y[i][j] = z[i][j];}
void fast(int k){//统一把这一次的乘积放x，方便之后处理
if (k == 0){
for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){ x[i][j] = 0;}x[i][i] = 1;}
return ;
}
if (k == 1){
for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++) x[i][j] = a[i][j];}
return ;
}
fast(k/2);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) y[i][j] = x[i][j];
m();
airbus();
fast(k%2);
m();
boeing();
}
signed main(){
int t;
cin >> t;
while (t–){
int k;
cin >> k;
if (k <= 3){ cout << "1\\n";continue;}
n = 3;
a[1][1] = 1;
a[1][3] = 1;
a[2][1] = 1;
a[3][2] = 1;
fast(k-3);//注意减3
memset(y,0,sizeof y);
y[1][1] = 1;
y[2][1] = 1;
y[3][1] = 1;
int ans = 0;
for (int k = 1; k <= 3; k++) (ans += x[1][k]*y[k][1]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
cout << ans << "\\n";
}
return 0;
}
P1349:
其实就是把系数改一下就行：
#include <bits/stdc++.h>
using namespace std;
#define int long long
int The_Boeing_757_is_the_best_aircraft_model_in_the_world;
int n;
int x[104][104];
int a[104][104];
int y[104][104];
int z[104][104];
int k,p,q,a1,a2;
void m(){
memset(z,0,sizeof(z));
for (int i = 1; i <= n; i++) for (int j = 1; j<= n; j++) for (int k = 1; k <= n; k++)(z[i][j] += x[i][k]*y[k][j]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
}
void boeing(){ for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) x[i][j] = z[i][j];}
void airbus(){for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) y[i][j] = z[i][j];}
void fast(int k){//统一把这一次的乘积放x，方便之后处理
if (k == 0){
for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){ x[i][j] = 0;}x[i][i] = 1;}
return ;
}
if (k == 1){
for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++) x[i][j] = a[i][j];}
return ;
}
fast(k/2);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) y[i][j] = x[i][j];
m();
airbus();
fast(k%2);
m();
boeing();
}
signed main(){
cin >> p >> q >> a1 >> a2 >> k >> The_Boeing_757_is_the_best_aircraft_model_in_the_world;
if (k == 1) {cout << a1; return 0;}
if (k == 2) {cout << a2; return 0;}
n = 2;
a[1][1] = p;
a[1][2] = q;
a[2][1] = 1;
fast(k-2);//和那个斐波那契数列同理
memset(y,0,sizeof y);
y[1][1] = a2;//别搞反了
y[2][1] = a1;
int ans = 0;
for (int k = 1; k <= 2; k++) (ans += x[1][k]*y[k][1]) %= The_Boeing_757_is_the_best_aircraft_model_in_the_world;
cout << ans;
return 0;
}
希望大家能把这5倍经验接好了：
广义斐波那契数列
斐波那契数列
矩阵加速（数列）
【模板】矩阵快速幂
矩阵乘法
OK啊今天就到这里了，希望大家已经大致的了解了矩阵乘法的作用！
