2025 Summer Day11

Content：矩阵 DP

Date：2025.7.27

Review

矩阵基本操作：link

Example1 - 洛谷-P1962 斐波那契数列

题目描述

给定 $n$ ，求斐波那契数列的第 $n$ 项 $f_n$ 。

f_n = \begin{cases} 1 & n = 0,1 \\ f_{n-1} + f_{n-2} & oterwise \end{cases}

数据范围： $n < 2^{63}$ 。

思路

首先显然 $O(n)$ 的递推是不行的了，我们考虑将递推式转化为矩阵乘法的形式：

\begin{aligned} \begin{bmatrix} f_{n - 1} \\ f_{n - 2} \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ \end{bmatrix} &= \begin{bmatrix} f_{n} \\ f_{n - 1} \end{bmatrix} \\ \\ \begin{bmatrix} f_{n - 2} \\ f_{n - 3} \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ \end{bmatrix}^2 &= \begin{bmatrix} f_{n} \\ f_{n - 1} \end{bmatrix} \\ &\dots \\ \begin{bmatrix} f_{0} \\ f_{1} \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^{n-2} &= \begin{bmatrix} f_{n} f_{n - 1} \end{bmatrix} \end{aligned}

这里只需要矩阵快速幂即可。复杂度 $O(log n)$ 。

提交记录：link

Example2 - UVA11270 Tiling Dominoes

题目描述 给定一个 $n \times m$ 的网格，求用 $1 \times 2$ 的方块覆盖网格的方案数。数据范围： $n \times m \le 100$ 。

思路

我们考虑轮廓线 DP，定义 $dp_{i,j,s}$ 表示当前修改的点是 $(i,j)$ ，其状态为 $s$ 。这里的 $s$ 和之前题目里的不同，它表示的是第 $i$ 行的前 $j-1$ 列的覆盖情况和第 $i - 1$ 行的后 $m - j + 1$ 列的覆盖情况，其中 $0$ 表示还未被覆盖， $1$ 表示已经被覆盖。

$dp$ 的第一维可以省略，所以转化为 $dp_{i,s}$ 表示考虑到第 $j$ 列，其状态为 $s$ 的方案数。

接下来考虑转移，设上一行的状态为 $s$ ，转移有三种。

当前位置不放，留空 (前提条件： $s >> j \ \& \ 1$ )： $dp_{i-1,s} \to dp_{i,s \oplus (1 << j)}$
当前位置横着放 (前提条件： $j > 0$ 且 $s >> j \ \& \ 1$ )： $dp_{i-1,s} \to dp_{i,s | (1 << (j - 1))}$
当前位置竖着放 (前提条件： $i > 0$ 且 $!(s >> j \& 1)$ )： $dp_{i-1,s \oplus (1 << j)} \to dp_{i, s}$ 。

这样就写完了。

Code

1
#include <bits/stdc++.h>
2

3
using std::cin;
4
using std::cout;
5

6
constexpr int N = 105;
7
int n, m;
8
long long dp[2][1 << 11];
9

10
int main() {
11
    std::ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
    cout.tie(nullptr);
14

15
    while (cin >> n >> m) {
16
        if (n < m) std::swap(n, m);
17

18
        int line = 0, max_status = 1 << m;
19
        std::memset(dp, 0, sizeof(dp));
20
        dp[line][max_status - 1] = 1;
21

22
        for (int i = 1; i <= n; i++) {
23
            for (int j = 0; j < m; j++) {
24
                line = !line;
25
                std::memset(dp[line], 0, sizeof(dp[line]));
26

27
                for (int status = 0; status < max_status; status++) {
28
                    if (status >> j & 1) {
29
                        dp[line][status ^ (1 << j)] += dp[!line][status];
30
                    }
31
                    if (j > 0 && (status >> (j - 1) & 1) == 0 && (status >> j & 1)) {
32
                        dp[line][status | (1 << (j - 1))] += dp[!line][status];
33
                    }
34
                    if (i > 0 && (status >> j & 1) == 0) {
35
                        dp[line][status | (1 << j)] += dp[!line][status];
36
                    }
37
                }
38
            }
39
        }
40

41
        cout << dp[line][max_status - 1] << '\n';
42
    }
43

44
    return 0;
45
}

Example3 - 洛谷-P5678 河神

思路

我们一样考虑将递推式转化成矩阵乘法的形式。

但是这里我们注意到地推中的操作是 $|$ 和 $\&$ ，所以哦我们要做 $(|,\&)$ 矩阵乘法 (这个需要证明 $|$ 操作对 $\&$ 操作具有分配律，这里就不证明了)。

\begin{bmatrix} a_{n - 1} & a_{n-2} & a_{n-3} & \dots & a_{n-k} \end{bmatrix} \times \begin{bmatrix} b_{n-1} & b_{n - 2} & b_{n - 3} & \dots & b_1 & b_0 \\ -1 & 0 & 0 & \dots & 0 & 0 \\ 0 & -1 & 0 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & -1 & 0 \end{bmatrix} = \begin{bmatrix} a_n & a_{n - 1} & a_{n - 2} & \dots & a_{n - k + 1} \end{bmatrix}

所以就可以使用矩阵快速幂了。

提交记录：link。