当前位置: 首页 > news >正文

OI集训 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\),转移有三种。

  1. 当前位置不放,留空 (前提条件:\(s >> j \ \& \ 1\)):\(dp_{i-1,s} \to dp_{i,s \oplus (1 << j)}\)
  2. 当前位置横着放 (前提条件:\(j > 0\)\(s >> j \ \& \ 1\)):\(dp_{i-1,s} \to dp_{i,s | (1 << (j - 1))}\)
  3. 当前位置竖着放 (前提条件:\(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。

http://www.wuyegushi.com/news/771.html

相关文章:

  • 实操使用 go pprof 对生产环境进行性能分析(问题定位及代码优化)
  • 7 月 27 日 模拟赛总结 - sb
  • 推挽输出和开漏输出
  • 深入 JavaScript 运行原理
  • Combinatorics 第二弹
  • DAY23
  • ES 多租户隔离技术
  • P2601 [ZJOI2009] 对称的正方形
  • 7/25
  • JAVA注解处理
  • day4
  • 30天总结-第二十七天
  • AWS WAF全新控制台体验:简化安全配置与实时威胁监控
  • [题解]GDOI2014
  • 从代码堆砌到工程思维:读《构建之法》的蜕变思考
  • 初遇框架
  • 2025/7/27 模拟赛总结
  • 扣子Coze智能体万字教程:从入门到精通,一文掌握AI工作流搭建
  • STM32简介 - LI,Yi
  • 数学相关学习笔记
  • 第二天
  • 【图论】总结 10:无向图的必经边与必经点
  • 准备去北京
  • 英国拟立法限制iOS与Android垄断地位,强制开放移动生态
  • vmware虚拟机安装
  • 通过Python交互式控制台理解Conv1d
  • 多Agent协作入门:群聊编排模式
  • nreset
  • 7月27号
  • 4