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

推出 $\begin{bmatrix}a & 1 \\0 & 1\end{bmatrix}\times\begin{bmatrix}x_0 \\c \end{bmatrix}=\begin{bmatrix}x_1 \\c \end{bmatrix}$。

solved on 2025/2/17

问题：快速幂终于写对了，但是最后乘上初始矩阵的时候我写的是 ans=(anss.a[0][0]*x+c)%m。这是错的，因为我没有正确理解矩阵快速幂的原理。

操作序列看成循环节，比如 $t=40$，循环节长度为 $6$ 就把操作合起来做 $6$ 次再单独做 $4$ 次。

如果操作序列长度不一样，就把他们的 $\text{lcm}$ 次合起来做。

和上题思路差不多，发现 $2,3,4$ 的 $\text{lcm}$ 是 $12$，所以每过 $12$ 秒食人鱼就回到了原来的位置，把 $12$ 做成循环节，搞 $12$ 个矩阵，合在一起快速幂，剩下的单独做就行。

三个人构造相邻两天的矩阵

把 $ans$ 和 $x$ 压成一个矩阵

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

暴力 dp 非常简单。

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

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

不难，但是没记完。

暴力是分层图最短路。

$f_{i,k}$ 表示从 $1$ 到 $i$ 用了 $k$ 次的最短路。

$f_{i,j,x}$ 用 $x$ 次，从 $i$ 到 $j$ 的最短路。

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

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

设矩阵 $C$。

广义矩阵乘法。

也是广义矩阵乘法。

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