柒葉灬 的博客

柒葉灬 的博客

矩阵乘法(个人笔记)

posted on 2018-12-23 22:24:00 | under 专题总结 |

矩阵乘法


矩阵乘法就是 $2$ 个矩阵相乘。

如果 矩阵 $A$ 是 $n$ 行 $p$ 列 ,矩阵 $B$ 是 $p$ 行 $m$ 列 , $C=A*B $ ,那么矩阵 $C$ 是 $n$ 行 $m$ 列

其中,矩阵 $C$ 的 $i$ 行 $j$ 列是这样算的↓,(代码更能解释清楚)

void calc(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=p;k++)
                C[i][j]+=A[i][k]*B[k][j];
}

上面的代码可以看出,矩阵乘法是 $O(n^3)$ 的


矩阵乘法满足结合律,分配律不满足交换律

利用结合律和分配律,我们可以利用矩阵乘法解决很多问题。

例如 : 结合律 -> 矩阵快速幂

例子:求第 $n$ 项的斐波拉契数列,对 $1e9+7$ 取模。

$\begin{bmatrix} 1&1\\1&0\end{bmatrix}$ $\times$ $\begin{bmatrix} f(n-1)\\f(n-2)\end{bmatrix}$ = $\begin{bmatrix} f(n-1)+f(n-2)\\f(n-1)\end{bmatrix}$ = $\begin{bmatrix} f(n)\\f(n-1)\end{bmatrix}$

所以对于求 $f(n)$ 我们可以这么写:

$\begin{bmatrix} f(n)\\f(n-1)\end{bmatrix}$ = ${\begin{bmatrix} 1&1\\0&1\end{bmatrix}}^{n-2}$ $\times$ $\begin{bmatrix} f(2)\\f(1)\end{bmatrix}$

${\begin{bmatrix} 1&1\\0&1\end{bmatrix}}^{n-2}$ 显然用矩阵快速幂求一下就行了。


矩阵快速幂模板:

matrix qpow(matrix p,int q){
    matrix res;
    for(int i=1;i<=n;i++)
        res.a[i][i]=1;
    while(q){
        if(q&1)res=res*p;
        p=p*p;
        q>>=1;
    }
    return res;
}

补充一下为什么初始矩阵是一个由左上角到右下角为 $1$ 的矩阵, 因为这个矩阵是单位矩阵,相当于 $1$ , 矩阵 $A$ * 单位矩阵 = 矩阵 $A$


矩阵 $ans$ = $pow($ 矩阵 $tmp,K) \times$ 矩阵 $begin$ ;

若状态 $i$ 能转移到状态 $j$ , $tmp.a[j][i]++;$


特殊的矩阵:相伴矩阵。

相伴矩阵也是循环矩阵,如果已知第一行,那么 $n$ 行的信息也知道了(因为信息一样,只是位置变了),遇到这种矩阵要注意,这种矩阵可以使 $O(n^3)$ 的矩阵乘法变成 $O(n^2)$ (因为少算了 $n-1$ 行)

例题:专题G


多次方相加

我们需要求下面一个式子:

$$ x^1+x^2+x^3+x^4+x^5+x^6 $$

利用二分的思想我们可以得到:

$$ x^1+x^2+x^3+x^3*(x^1+x^2+x^3)$$

$$ (x^1+x^2+x^3)*(1+x^3) $$

递归处理即可。

同样,因为矩阵乘法满足分配律的性质,所以同样可以这么写。

注意,如果 $(1+x^3)$ 部分用了矩阵快速幂,那么复杂度就会达到 $O(log^2n)$ 。

有些题目不能这么写,所以不能快速幂,需要预处理(略)。复杂度降为 $O(logn)$

例题:专题L


矩阵乘法适用于状态转移多次,尤其是计数问题的时候,只要状态定义的好,那么套上矩阵乘法优化,就可以轻松解决了。

例题:专题M


矩阵乘法还可以适用于多米诺骨牌这类转移状态问题,只要把边连上套个矩阵快速幂就行了

例题:专题N