- BC20260025's blog
6.1信息笔记（矩阵入门）
-
BC20260025
LV 6
@
2024-6-1 12:20:26
矩阵乘法和矩阵快速幂
概念
对角矩阵： 除了主对角线以外都是 的方阵称为对角矩阵。
单位矩阵： 主对角线全部是 ，其他元素全部是 的方阵。它在乘法里的作用和数学里数字 的作用类似，因此称为单位矩阵。
三角矩阵： 主对角线某一侧元素都是 的方阵。如果主对角线左下方元素都是 ，称为上三角矩阵，否则称为下三角矩阵。
单位三角矩阵： 主对角线都是 ，且某一侧元素都是 的方阵。
对称矩阵： 满足 的矩阵称为对称矩阵。常见例子：无向图的邻接矩阵。
矩阵乘法
函数写法
# include<iostream>
# include<cstring>
using namespace std;
const int N=103,mod=1e9+7;
int n;
long long k;
struct jz{
long long a[N][N];
jz(){
memset(a,0,sizeof(a));
}
void init(){
for(int i=1;i<=n;++i)
a[i][i]=1;
}
void in(){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>a[i][j];
}
void out(){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
}A;
jz mul(jz x,jz y){
jz z;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int l=1;l<=n;++l)
z.a[i][j]=(z.a[i][j]+(x.a[i][l]%mod)*(y.a[l][j]%mod)%mod)%mod;
return z;
}
jz qpow(jz x,long long k){
jz ans;
ans.init();
while(k){
if(k&1) ans=mul(ans,x);
x=mul(x,x);
k>>=1;
}
return ans;
}
int main(){
cin>>n>>k;
A.in();
qpow(A,k).out();
return 0;
}
重载运算符写法
# include<iostream>
# include<cstring>
using namespace std;
# define ll long long
const int N=103,mod=1e9+7;
int n;
ll k;
struct mat{
ll a[N][N];
mat(){memset(a,0,sizeof(a));}
void init(){
for(int i=1;i<=n;++i)
a[i][i]=1;
}
void in(){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>a[i][j];
}
void out(){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
mat operator*(mat T) const{
mat res;
int r;
for(int i=1;i<=n;++i)
for(int k=1;k<=n;++k){
r=a[i][k];
for(int j=1;j<=n;++j)
res.a[i][j]=(res.a[i][j]+T.a[k][j]*r)%mod;
}
return res;
}
mat operator^(ll k) const{
mat res,bas;
res.init();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
bas.a[i][j]=a[i][j]%mod;
while(k){
if(k&1) res=res*bas;
bas=bas*bas;
k>>=1;
}
return res;
}
}A;
int main(){
cin>>n>>k;
A.in();
(A^k).out();
return 0;
}
矩阵乘幂
定义和数字的乘幂相同，显然只有方阵能这么定义。
既然有乘幂，就自然有快速幂。
快速幂的方法和整数快速幂基本一致。
建议把矩阵给手写一个类，然后用重载运算符和函数的方法来写，会方便很多。
应用：
- 在线性递推中，可以将有用的状态存在一个矩阵中，通过状态矩阵和状态转移矩阵相乘可以得到下一个状态，如果需要做多次这样的重复乘法，那么可以使用快速幂来进行加速。
- 另外就是图论中使用邻接矩阵的一些题目，例如指定边数的路径数量等，也可以用矩阵快速幂优化。
例题
1. 斐波那契第n项
题面
在数列 中，，输入 和 ，求 。
数据范围：。
代码
参考代码
# include<iostream>
# include<cstring>
using namespace std;
const int mod=1e9+7;
long long n;
struct jz{
long long a[3][3];
jz(){
memset(a,0,sizeof(a));
}
void init(){
for(int i=1;i<=2;++i)
a[i][i]=1;
}
}A,B;
jz mul(jz x,jz y){
jz z;
for(int i=1;i<=2;++i)
for(int j=1;j<=2;++j)
for(int l=1;l<=2;++l)
z.a[i][j]=(z.a[i][j]+(x.a[i][l]%mod)*(y.a[l][j]%mod)%mod)%mod;
return z;
}
jz qpow(jz x,long long k){
jz ans;
ans.init();
while(k){
if(k&1) ans=mul(ans,x);
x=mul(x,x);
k>>=1;
}
return ans;
}
int main(){
cin>>n;
if(n==1){
cout<<1;
return 0;
}
A.a[1][1]=A.a[1][2]=A.a[2][1]=1;
B=qpow(A,n-2);
cout<<(B.a[1][1]+B.a[1][2])%mod;
return 0;
}
2. 斐波那契前n项和
题面
在数列 中，，令 ，输入 和 ，求 。
数据范围：。
3. [SCOI2009]迷路
分析
题目给出的实际上就是邻接矩阵。
如果边权只有 和 ，那么问题很简单。以前讲过，这种邻接矩阵的 次方的 元素就是 到 的经过 条边的路径数量，即通过时间为 的路径数量。
所以这个时候直接矩阵快速幂就可以了。
但是本题边权在 之间。。。咦 啊，直接拆点。
把所有点拆成 个，记 为 号点拆出来的第 个，我们从所有的 向 连一条边权为 的有向边，对任何一条从 到 的边权为 的有向边，我们从 向 连一条边权为1的有向边。这样的话所有边都是 和 且任何 到 的路径长度都等于原图中 到 的路径长度。
利用上面的转化，图的结点数不超过 ，而且邻接矩阵的边权都是 和 ，于是可以直接沿用上面的矩阵快速幂方法即可。
4. [HNOI2008]GT考试
分析
考虑DP。
状态：dp[i][j]表示考虑准考证号的前i位，目前匹配到不吉利数字的第j位的方案总数。
转移方程：dp[i][j]=sum{dp[i-1][p]}，p根据匹配情况的不同而不同。
这样不好优化，我们换个方法写：
dp[i][j]=sum{dp[i-1][k]*g[k][j] | k=0,1,...,m-1}
这里g[k][j]表示一个匹配了长度为k的串，有多少种加数字的方法使得匹配长度变为j。
由于g只和不吉利的数字有关，因此我们可以KMP预处理g数组，在求出next数组后，枚举匹配长度k和前缀ch，暴力计算能匹配到多少的前缀。
然后g这个数组就是一个常量矩阵了，可以用矩阵快速幂来转移dp数组。
作业