腾飞计划寒假第三课——矩阵快速幂&矩阵快速幂优化dp 2025/2/4

· · 个人记录

P2044 [NOI2012] 随机数生成器

推出

solved on 2025/2/17 问题：快速幂终于写对了，但是最后乘上初始矩阵的时候我写的是 `ans=(anss.a[0][0]*x+c)%m`。这是错的，因为我没有正确理解矩阵快速幂的原理。 ### [P10498 石头游戏](https://www.luogu.com.cn/problem/P10498) 操作序列看成循环节，比如 $t=40$，循环节长度为 $6$ 就把操作合起来做 $6$ 次再单独做 $4$ 次。 如果操作序列长度不一样，就把他们的 $\text{lcm}$ 次合起来做。 ### [P2579 [ZJOI2005] 沼泽鳄鱼](https://www.luogu.com.cn/problem/P2579) 和上题思路差不多，发现 $2,3,4$ 的 $\text{lcm}$ 是 $12$，所以每过 $12$ 秒食人鱼就回到了原来的位置，把 $12$ 做成循环节，搞 $12$ 个矩阵，合在一起快速幂，剩下的单独做就行。 ### [P1707 刷题比赛](https://www.luogu.com.cn/problem/P1707) 三个人构造相邻两天的矩阵 $\begin{bmatrix}0&1&0&0&0&0&0&0&0&0&0\\q&p&0&1&0&1&r&t&1&0&0\\0&0&0&1&0&0&0&0&0&0&0\\0&1&v&u&0&1&0&0&0&1&0\\0&0&0&0&0&1&0&0&0&0&0\\0&1&0&1&y&x&0&1&2&0&1\\0&0&0&0&0&0&1&2&1&0&0\\0&0&0&0&0&0&0&1&1&0&0\\0&0&0&0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&0&0&w&0\\0&0&0&0&0&0&0&0&0&0&z\end{bmatrix}\times\begin{bmatrix}a_k\\a_{k+1}\\b_k\\b_{k+1}\\c_k\\c_{k+1}\\k^2\\k\\1\\w^k\\z^k\end{bmatrix}=\begin{bmatrix}a_{k+1}\\a_{k+2}\\b_{k+1}\\b_{k+2}\\c_{k+1}\\c_{k+2}\\(k+1)^2\\k+1\\1\\w^{k+1}\\z^{k+1}\end{bmatrix}

P3216 [HNOI2011] 数学作业

把 ans 和 x 压成一个矩阵

\begin{bmatrix}10&1&0\\0&1&1\\0&0&1\end{bmatrix}\times\begin{bmatrix}ans\\x\\1\end{bmatrix}=\begin{bmatrix}nextans\\x+1\\1\end{bmatrix}

多位数分开计算，一位数算一遍，算完之后把 10 改成 100 算两位数，再改成 1000 算三位数，最多 18 位。

P3990 [SHOI2013] 超级跳马

暴力 dp 非常简单。

就是维护一个前缀和，g_{i,j}表示与其奇偶性相同的 f_{k,j} 的和，即 g_{i,j}=f_{i,j}+f_{i-2,j}+f_{i-4,j}。

f_{i,j}=g_{i-1,j}+g_{i-1,j-1}+g_{i-1,j+1} g_{i,j}=g_{i-2,j}+f_{i,j}

矩阵优化时维护 g 和 f，g 和 f 固定在同一个矩阵里，像 P1707 一样推状态转移矩阵。

CF1117D Magic Gems

不难，但是没记完。

P6190 [NOI Online #1 入门组] 魔法

暴力是分层图最短路。

$f_{i,k}=\min(f_{j,k-1}-a_{j,i},f_{j,k}+a_{j,i}) $f_{i,j,k}=\min(f_{i,k,x-1}+f_{k,j,1})

设 A=f_{i,j,1}，B=f_{i,j,x}

形如 B=\min(B+A)。

设矩阵 C。

C_{i,j}=min(B_{i,k}+A_{k,j})

广义矩阵乘法。

P5678 [GZOI2017] 河神

也是广义矩阵乘法。

形如 C_{i,j}=\bigoplus(B_{i,k}\ \bigotimes\ A_{k,j})。