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
#include <bits/stdc++.h>using std::cin;
using std::cout;constexpr int N = 105;
int n, m;
long long dp[2][1 << 11];int main() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);while (cin >> n >> m) {if (n < m) std::swap(n, m);int line = 0, max_status = 1 << m;std::memset(dp, 0, sizeof(dp));dp[line][max_status - 1] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < m; j++) {line = !line;std::memset(dp[line], 0, sizeof(dp[line]));for (int status = 0; status < max_status; status++) {if (status >> j & 1) {dp[line][status ^ (1 << j)] += dp[!line][status];}if (j > 0 && (status >> (j - 1) & 1) == 0 && (status >> j & 1)) {dp[line][status | (1 << (j - 1))] += dp[!line][status];}if (i > 0 && (status >> j & 1) == 0) {dp[line][status | (1 << j)] += dp[!line][status];}}}}cout << dp[line][max_status - 1] << '\n';}return 0;
}
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。