浅谈矩阵乘法的应用

前言

矩阵乘法,常常被用作递推式的优化,如果把一个递推式一步的递推转换成乘上一个矩阵,那么由于矩阵乘法有结合律,所以我们就可以快速幂啦,起到优化的效果。而递推式出现最多的地方当然就是dp了,所以今天想简单的总结一下矩阵乘法优化dp。

正文

博主做的题比较少,见到的这类题也比较少,但有一道题感觉还是比较经典的。
给出一张有向图,问从1号点出发,走过路径长度为T,到达n号点的方案数,其中$T\le 2e9$,每条边的边权均为1,$n\le100$。

那么显然有dp,$f[i][j]$表示到第j个点,当前走过的路径长度为i的方案数,那么我们枚举j的所有出边,设终点为k,则$f[i+1][k]+=f[i][j]$。
但是这样子不方便我们理解矩阵乘法,我换一种dp方式,$f[i][j][k]$表示从j到k走了i条边的方案数,然后我们把给我们的邻接矩阵定义为map好了,那么首先$f[1][j][k]$就对应了map对吧,因为你只能走一步,当然只能走map上的边咯。接下来我们考虑转移,我们$f[i][j][k]$能由什么得到,我们显然是从k出发倒退一步对吧,假设上一步我们是$p\to k$,那么$f[i-1][j][p]\to f[i][j][k]$对吧,我们把这个dp的式子用代码写出来。

1
2
3
4
5
6
7
8
9
for (int i=1;i<=T;i++){
for (int j=1;j<=n;j++){
for (int k=1;k<=n;k++){
for (int p=1;p<=n;p++){
if (map[p][k]==1) f[i][j][k]+=f[i-1][j][p];
}
}
}
}

然后神奇的事情就要发生了,我们把这个式子变一下形

1
2
3
4
5
6
7
8
9
for (int i=1;i<=T;i++){
for (int j=1;j<=n;j++){
for (int k=1;k<=n;k++){
for (int p=1;p<=n;p++){
f[i][j][k]+=f[i-1][j][p]*map[p][k];
}
}
}
}

如果map[p][k]是0的话*0没有影响,如果是1的话没有区别对吧。
再仔细观察一下这个式子,是不是发现和矩乘的形式一模一样。
我们把i单独拎出来,那么f[i]这个矩阵就是由f[i-1]这个矩阵乘上map矩阵得到的,是不是非常神奇,接下来问题就好办了。
前面已经说过f[1]就是map,所以我们要求走T步,只要把map矩阵自乘T次得到ans,ans[1][n]就是最终答案了。

这道题经典就在于它的递推矩阵正是map矩阵本身,非常神奇,许多人知道这个结论,但是并不知道是怎么来的,希望上文能够帮助大家理解。

而其他题目dp的矩阵就因题而异了,博主由于水平的问题也讲不出更多了,然后有一道非常好的例题给大家安利一下。
Luogu 1297
SCOI2009 迷路
简述一下题意,就是有一张有向图,每条边有边权,注意不再是1,但是边权的范围1..9,然后走T的长度,问从1到n的方案数。
$T\le 1000000000$
如果边权不是1的话,用上面的转移就不对了,那怎么办,数据范围这么大,不矩乘不行啊,而边权又这么小,我们是不是可以把边权变成1。
我们把每个点x变成$x[1]…x[9],map[x[i]][x[i+1]]=1$,然后如果$x\to y$有一条边权为t的边,我们就令$map[x[t]][y[1]]=1$,这样子我们就保证了从x走到y要花t的时间,然后边权也都被我们变成1了,这样我们再和上面一样做就行了。
希望本文对大家有帮助,以上全是基于博主的个人见解,如果有错误或者建议非常欢迎在评论留言,感激不尽。