矩阵乘法与递推应用

矩阵

本质是一个二维数表

$$\mathbf A=\begin{bmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{1,n} \\ \vdots &\vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n} \\ \end{bmatrix}$$

矩阵乘法

$\mathbf A$ 为 $m \times n$ 的矩阵，$\mathbf B$ 为 $n \times p$ 的矩阵，$\mathbf C = \mathbf A \times \mathbf B$，$\mathbf C$ 中第 $i$ 行第 $j$ 列元素可以表示为：

$$c_{i,j}=\sum_{k=1}^{n}a_{i,k}\times b_{k,j}$$

示例：

$$\begin{aligned} \begin{bmatrix} 1 & 2 & 5\\ 3 & 4 & 6\\ \end{bmatrix} \times \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} &= \begin{bmatrix} (1\times7+2\times9+5\times11)&(1\times8+2\times10+5\times12)\\ (3\times7+4\times9+6\times11)&(3\times8+4\times10+6\times12)\\ \end{bmatrix} \\ &= \begin{bmatrix} 80 & 88\\ 123 &136\\ \end{bmatrix} \end{aligned}$$

换句话说，就是用矩阵 $\mathbf A$ 的第 $i$ 行元素乘矩阵 $\mathbf B$ 的第 $j$ 列元素求和。

广义矩阵乘法

$$c_{i,j}=\min _{k=1}^{n}(a_{i,k}+b_{k,j}) \\ c_{i,j}=\sum _{k=1}^{n}\max(a_{i,k},b_{k,j}) \\ \vdots$$

广义矩阵乘法可以是自行定义的运算，可以用来解决各种递推问题。但要保证满足结合律，以使用矩阵快速幂。

矩阵乘法的性质

事实上，矩阵乘法满足幺半群的性质。

1. 矩阵乘法有封闭性：
   显然，矩阵与矩阵相乘，得到的还是矩阵。

2. 矩阵乘法有结合律：

   $$\mathbf D = \mathbf A \times \mathbf B \times \mathbf C = \mathbf A \times \left( \mathbf {B} \times \mathbf {C} \right)$$

   尝试从代数角度进行证明

   $$\begin{aligned} d_{i,j}&=\sum_{l=1}^{\mathbf B_{col}}\left(\sum_{k=1}^{\mathbf B_{row}}\left(a_{i,k}\times b_{k,l}\right)\times c_{l,j} \right)\\ &=\sum_{l=1}^{\mathbf B_{col}}\sum_{k=1}^{\mathbf B_{row}}a_{i,k}\times b_{k,l}\times c_{l,j}\\ &=\sum_{k=1}^{\mathbf B_{row}}a_{i,k}\times \left(\sum_{l=1}^{\mathbf B_{col}}b_{k,l}\times c_{l,j} \right) \end{aligned}$$

3. 矩阵乘法存在幺元
   定义单位矩阵

   $$\mathbf I_n = \begin{bmatrix}1 & 0 &\dots & 0\\ 0 & 1 &\dots & 0\\\vdots & \vdots &\ddots & \vdots\\ 0 & 0 &\dots & 1\\\end{bmatrix}$$

则有$\mathbf A\times \mathbf I_n = \mathbf A$。

矩阵快速幂

洛谷P3390 【模板】矩阵快速幂

由于矩阵乘法满足结合律，可以利用倍增的思想，在对数复杂度内解决矩阵幂运算的问题。代码复杂度 $O(n^3\log k)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 105;
const ll MOD = 1e9+7;

struct Matrix{
    int row,col;
    ll d[N][N];
    Matrix(int r,int c){
        row=r,col=c;
        memset(d,0,sizeof(d));
    }
};

Matrix time(Matrix a,Matrix b){
    Matrix c(a.row,b.col);
    if(a.col != b.row)return c;
    for(int i=0;i<a.row;i++){
        for(int j=0;j<b.col;j++){
            for(int k=0;k<a.col;k++){
                c.d[i][j] += a.d[i][k] * b.d[k][j];
                c.d[i][j] %= MOD;
            }
        }
    }
    return c;
}

Matrix pow(Matrix a,ll p){
    Matrix res(a.col,a.col);
    for(int i=0;i<a.col;i++){
        res.d[i][i]=1;
    }

    while(p>0){
        if(p&1)res=time(res,a);
        p>>=1;
        a=time(a,a);
    }
    return res;
}



int main(){
    ll n,k;
    scanf("%lld%lld",&n,&k);
    Matrix a(n,n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a.d[i][j]);
        }
    }

    auto ans = pow(a,k);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%lld ",ans.d[i][j]);
        }
        puts("");
    }
    return 0;
}

矩阵快速幂加速递推

洛谷P1962 斐波那契数列

题意：求斐波那契数列第$n$项对$10^9+7$求余的结果，$n<2^{63}$。
显然如果递推的话，复杂度 $O(n)$，肯定会超时。
这时，我们考虑用矩阵乘法加速。
由递推式$F_n=F_{n-1}+F_{n-2}$，我们可以列出如下等式：

$$\begin{bmatrix}F_n & F_{n-1}\end{bmatrix} = \begin{bmatrix}F_{n-1} & F_{n-2}\end{bmatrix} \times \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}$$

则

$$\begin{bmatrix}F_n & F_{n-1}\end{bmatrix} = \begin{bmatrix}F_2 & F_1\end{bmatrix} \times \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{n-2}$$

时间复杂度 $O(\log n)$

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const ll MOD = 1e9+7;

struct Matrix{
    int row,col;
    ll d[5][5];
    Matrix(int r,int c){
        row=r,col=c;
        memset(d,0,sizeof(d));
    }
};
Matrix time(Matrix a,Matrix b){
    Matrix c(a.row,b.col);
    if(a.col != b.row)return c;
    for(int i=0;i<a.row;i++){
        for(int j=0;j<b.col;j++){
            for(int k=0;k<a.col;k++){
                c.d[i][j] += a.d[i][k] * b.d[k][j];
                c.d[i][j] %= MOD;
            }
        }
    }
    return c;
}
Matrix pow(Matrix a,ll p){
    Matrix res(a.col,a.col);
    for(int i=0;i<a.col;i++){
        res.d[i][i]=1;
    }

    while(p>0){
        if(p&1)res=time(res,a);
        p>>=1;
        a=time(a,a);
    }
    return res;
}

int main(){
    ll n;
    scanf("%lld",&n);
    if(n<=2){
        puts("1");
        return 0;
    }
    Matrix a(2,2);
    a.d[0][0]=a.d[0][1]=a.d[1][0]=1;
    Matrix b(1,2);
    b.d[0][0] = b.d[0][1] = 1;
    auto ans = time(b,pow(a,n-2));
    printf("%lld\n",ans.d[0][0]);
    return 0;
}

求斐波那契数列前 $n$ 项和

此时，有两个递推式$F_n=F_{n-1}+F_{n-2}$，$S_n=S_{n-1}+F_{n}$。我们可以将两个递推式写在同一个等式中。

$$\begin{bmatrix}F_n & F_{n-1} & S_n\end{bmatrix} = \begin{bmatrix}F_{n-1} & F_{n-2} & S_{n-1}\end{bmatrix} \times \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}$$

[HDU2157]How many ways??

题意：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值。
有递推式

$$F_{u,k} = \sum_{(v,u)\in E}F_{v,k-1}$$

可以构建如下矩阵

$$\begin{bmatrix}F_{1,k} & F_{2,k} & \dots & F_{n,k}\end{bmatrix}=\begin{bmatrix}F_{1,k-1} & F_{2,k-1} & \dots & F_{n,k-1}\end{bmatrix} \times \begin{bmatrix} a_{1,1} & a_{2,1} & \dots & a_{n,1} \\ a_{1,2} & a_{2,2} & \dots & a_{n,2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1,n} & a_{2,n} & \dots & a_{n,n} \\ \end{bmatrix}$$

其中 $a_{i,j}$ 为从 $i$ 到 $j$ 的边的个数，在没有重边的情况下，这个矩阵正好等于这张图的邻接矩阵。

[POJ3613]恰好k步最短路

题意：给定一个有向带权图，问从A点恰好走k步（允许重复经过边）到达B点的最短路。
有递推式

$$F_{u,k} = \min_{(v,u)\in E}(F_{v,k-1}+w_{u,v})$$

考虑定义矩阵乘法

$$c_{i,j}=\min _{k=1}^{n}(a_{i,k}+b_{k,j}) \\$$

则有

$$\begin{bmatrix}F_{1,k} & F_{2,k} & \dots & F_{n,k}\end{bmatrix}=\begin{bmatrix}F_{1,k-1} & F_{2,k-1} & \dots & F_{n,k-1}\end{bmatrix} \times \begin{bmatrix} w_{1,1} & w_{2,1} & \dots & w_{n,1} \\ w_{1,2} & w_{2,2} & \dots & w_{n,2} \\ \vdots & \vdots & \ddots & \vdots \\ w_{1,n} & w_{2,n} & \dots & w_{n,n} \\ \end{bmatrix}$$

问题解决。