矩阵乘法是一种常见的递推优化

矩阵乘法基础

  • 矩阵乘法的计算: 前一个矩阵的一列上的每个数分别乘上后一个矩阵的一行的每个数, 得到的结果加起来放在结果矩阵这一行一列的交点位置
  • 矩阵乘法满足的条件: 前一个矩阵的列数 = 后一个矩阵的的行数
  • 矩阵乘法的性质:
    • 没有交换律
    • 满足结合律
    • 满足乘法分配律 $(A + B) \times C = A \times C + B \times C$
    • 转置 $(A \times B) ^ T = B ^ T \times A ^ T$
  • 乘法的代码
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];
    }
  }
}

矩阵乘法几点应用

优化递推

几个栗子

$1$ . 求斐波那契数列的第$n(n <= 10^9)$项mod q
递推? 通项公式?

矩乘!
观察$F[i] = F[i - 1] + F[i - 2]$发现可以只由前两项得出(废话)
于是可以构造一个矩阵$A = (F[i] F[i - 1])$代表第$i$项斐波那契数, 如何得出$F[i + 1]$和$F[i]$?
构造矩阵$B$使得$A \times B = C \cap C = (F[i + 1], F[i])$即可!
怎么构造$B$ ? …这就因题而异了…
这道题里就是
$$
B = \begin{bmatrix}
1 & 2\\
0 & 1
\end{bmatrix}
$$
, 易看出$A$每乘一遍$B$都能得出下一项, 又因为矩乘满足结合律, 于是得出$F[n] = A \times B ^ {n - 2}$
但是复杂度依然没变啊…乘方…想到了什么?
快速幂!
前面说过矩阵是可以快速幂的, 于是复杂度就优化为了$O(\log n)$?
矩乘快速幂优化fib:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define REFUN (1000000007)
using namespace std;
struct matrix
{
    LL zh[2][2];
    void init()
    { zh[0][0] = zh[0][1] = zh[1][0] = zh[1][1] = 0; }
    matrix() {}
    matrix(bool x)
    {
        if (x)    zh[0][0] = zh[0][1] = zh[1][0] = 1, zh[1][1] = 0;
        else    zh[0][0] = zh[1][1] = 1, zh[1][0] = zh[0][1] = 0;
    }
};
matrix cheng(matrix x, matrix y)
{
    matrix re;
    re.init();
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                re.zh[i][j] += (x.zh[i][k] * y.zh[k][j]) % REFUN, re.zh[i][j] %= REFUN;
    return re;
}
matrix ksm(LL b)
{
    if (b == 0)
        return matrix(0);
    if (b == 1)
        return matrix(1);
    matrix re = ksm(b >> 1);
    re = cheng(re, re);
    if (b & 1)
        re = cheng(re, matrix(1));
    return re;
}
int main()
{
    int fib[5] = {0, 1, 1, 2, 3};
    LL n;
    scanf("%lld", &n);
    if (n < 5)
    {
        printf("%d", fib[n]);
        return 0;
    }
    printf("%lld", ksm(n).zh[1][0]);
    return 0;
}

// 1 1 2 3 5 8 13 21 34

$1.5$. 上一个题如果加一个常数呐?

把矩阵的对角线扩大一位即可, 横竖都填零, 对角线上的那个点填常数即可

$2$ . 如果递推式的项不连续呐? 比如$F[n] = F[n - 1] + F[n - 2] + F[n - 4]$
$A$保留3位?

$A$矩阵的大小得是4, 虽然 $F[n]$ 用不到 $F[n - 3]$ 但是递推到 $F[n + 1]$ 就用到了啊, 只要构造好$B$矩阵, 使相乘的时候 $F[n - 3]$ 的贡献为 $0$ 即可

传送至 Luogu

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (3 + 5)
#define REFUN (1000000007)
#define LL long long
using namespace std;
struct matrix
{
    int n, m;
    LL zh[3][3];
    void init()
    { memset(zh, 0, sizeof(zh)); }
    matrix() {}
    matrix(int x)
    {
        memset(zh, 0, sizeof(zh));
        if (x > 0)
            n = m = 3, zh[0][0] = zh[1][1] = zh[2][2] = 1;
        else if (x == 0)
            n = 1, m = 3, zh[0][0] = zh[0][1] = zh[0][2] = 1;
        else
            n = m = 3, zh[0][1] = zh[1][2] = zh[2][0] = zh[2][2] = 1;
    }
};
matrix cheng(matrix x, matrix y)
{
    matrix re;
    re.init();
    re.n = x.n, re.m = y.m;
    for (int i = 0; i < x.n; i++)
    for (int j = 0; j < y.m; j++)
    for (int k = 0; k < x.m; k++)
        re.zh[i][j] += x.zh[i][k] * y.zh[k][j], re.zh[i][j] %= REFUN;
    return re;
}
matrix ksm(LL b)
{
    if (b == 0)
        return matrix(1);
    if (b == 1)
        return matrix(-1);
    matrix re = ksm(b >> 1);
    re = cheng(re, re);
    if (b & 1)
        re = cheng(re, matrix(-1));
    return re;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        LL n;
        scanf("%lld", &n);
        if (n == 1)
        {
            puts("1");
            continue;
        }
        printf("%d\n", cheng(matrix(0), ksm(n - 2)).zh[0][0]);
    }
    return 0;
}

$3$ . 求$F[n] = \sum_{i = 1 \to 10} a[i] \times F[n - i]$, $a[i]$ 输入
暴力? 前缀和?

输入的时候构造矩阵就行了啊..

//未完待续

在图论上的应用

又是几个栗子

$1$ . 一个无向图, 允许走回头路, 问从$A$到$B$走 $K$条路的方案数

DFS? BFS? Floyed?

把邻接矩阵(讲真这么长时间不用邻接矩阵真心想不出来这个方法) 和自己相乘1次, 得到的$G[i][j]$就是从 $i$到$j$走2条路有 $G[i][j]$种方案, 因为$G_k[i][j] = \sum G_{k - 1}[i][] \times G_{k - 1}[][j]$ , 相当于[$i$走到一个点中转到达 $j$的方案数]的总和
然后答案就是$G ^ k$咯

$1.5$ . 一个有向图, 允许走回头路, 问从$A$到$B$走 $K$ 条路的方案数

同上, 没错就是把邻接矩阵改成有向的就行(矩乘真是太棒了!)

$2$ . 一个无向图, 不允许走回头路, 问从$A$到$B$走 $K$条路的方案数

关于回头路的定义: 只要不是 [从 A 到 B, 接着从 B 到 A] 都不算回头路
DFS? BFS?

把无向边拆成两条有向边, 建一个$(2m) \times (2m)$的邻接矩阵$G$(把边看成点, 把点看成边), 只有两条边首尾相接的时候才把这两条边在矩阵上$G$相连
再做一个 $G^k$, 结了

想一想为什么: 我们要保证不走回头路, 就是要让矩阵中自己和自己不相连, 满足了这个剩下的就都跟$1$一样了…