矩阵那些事

· · 个人记录

什么是矩乘

一些好题

这里没什么板题，都是些比较妙的矩乘，逐步深入。

这是一个蒟蒻的刷题历程，大佬轻喷。

这里面的题目都没放代码，因为矩阵的代码一定要自己写一遍，每个人的都不一样的。

[NOI2012]随机数生成器

题目大意

给你很多数字：\text{m, a, c, x0 n, g} 和一个递推式：

x_{n + 1} = (a \times x_n + c) \% m

要你求 x_n \% g 的数值。

数据范围：n, m, a, c, x0 \le 10^{18}, n, m \ge 1, a, c, x0 \ge 0

题解

考虑暴力是很好想的，直接递推就行了。

但是显然过不了，这样的柿子就很矩乘好不。

可以令我们维护的矩阵为 :

\left[ \begin{matrix} x_i \\ c \end{matrix} \right] \times A = \left[ \begin{matrix} x_{i + 1} \\ c \end{matrix} \right]

那么 A 也很好求，就是 ： \left[ \begin{matrix} a & 1 \\ 0 & 1 \end{matrix} \right]

跑下矩阵快速幂就行了。

[USACO07NOV]Cow Relays G

题目大意

给定一张 T 条边的无向连通图，求从 S 到 E 经过 N 条边的最短路长度。

数据范围：1 \le N \le 10^6, 1 \le T \le 100, 1 \le u, v, w \le 1000

题解

还是先考虑暴力，我们可以对 "经过 1 \le i \le N 条边的最短路长度（全源"

那么这样会炸空间，我们考虑可以把第一位压掉，但是这样子就无法记录前面的，所以每次只能往后转移一次，也就是每次把初始的所有边都跑一遍，扩展一圈，这样跑 N 次就是答案了.

但是这样会炸空间(屁事好多),所有考虑需要这样实现( c 的长度是 a 的长度加 b 的长度,长度是指我们枚举的 i ):

c_{i, j} = min(c_{i, j}, a_{i, k} + b_{k, j});

这个每次转移是互不影响的,所以可以矩乘,然后就是一样的操作了.

这还是不能过!!!因为你 u,v 是可以达到 1000 的,所以你还要离散化.

[TJOI2017]可乐

题目大意

数据范围： $n,m \le 100, t \le 10 ^ 9

题解

考虑先枚举时间，每次可以简单的 dp 一下。

那么我们肯定不可以留下一个 t 的复杂度，但是你看 n 的数据范围，这一看就很矩乘。

那就矩乘呗，和上个题一样，不过唯一要注意的是自爆操作，这个操作只要把每个点向 0 连一条边就行了，0 没有任何出度。

[NOI2013]矩阵游戏

题目大意

给你 a, b, c, d, n, m

要你求满足以下递推式的 f_{n,m} 是多少。

f_{1,1} = 1 f_{i, j} = a \times f_{i, j - 1} + b \ (j \ne 1) f_{i, 1} = c \times f_{i - 1, m} + d \ (i \ne 1)

数据范围： 1 \le n, m \le 10^{1000000}, 1 \le a, b, c, d \le 10^9

题解

我们把 $2$ 种转移分开考虑： 第一种：可以以 $\left[ \begin{matrix} f_{i,j} \\ b \end{matrix} \right]$ 为初始矩阵， $\left[ \begin{matrix} a & 1 \\ 0 & 1 \end{matrix} \right]$ 去转移。 第二种：可以以 $\left[ \begin{matrix} f_{i,1} \\ d \end{matrix} \right]$ 为初始矩阵， $\left[ \begin{matrix} c & 1 \\ 0 & 1 \end{matrix} \right]$ 去转移。 然后就很尴尬了，因为 $2$ 种转移的初始矩阵不同。 那么在 $\text{[NOI2012]}$ 随机数生成器中，我们是用 $\left[ \begin{matrix} x_i \\ c \end{matrix} \right]$ 作为初始矩阵，而 $\left[ \begin{matrix} a & 1 \\ 0 & 1 \end{matrix} \right]$ 是我们转移的矩阵。 但是这个你也可以变一变。可以变成用 $\left[ \begin{matrix} x_i \\ 1 \end{matrix} \right]$ 作为初始矩阵，而 $\left[ \begin{matrix} a & 1 \\ c & 1 \end{matrix} \right]$ 是我们转移的矩阵。 这题也是一样，可以变成这样： 第一种：可以以 $\left[ \begin{matrix} f_{i,j} \\ 1 \end{matrix} \right]$ 为初始矩阵， $A:\left[ \begin{matrix} a & 1 \\ b & 1 \end{matrix} \right]$ 去转移。 第二种：可以以 $\left[ \begin{matrix} f_{i,1} \\ 1 \end{matrix} \right]$ 为初始矩阵， $B:\left[ \begin{matrix} c & 1 \\ d & 1 \end{matrix} \right]$ 去转移。 这也初始矩阵就相同了，接下来就是 $A$ 用 $n$ 列，每列用了 $m - 1$ 次，B一共用了 $n - 1$ 次。 但是不可以直接那么做，需要： ```cpp A = qpow(A, m - 1), B = qpow(A * B, n - 1) * A; Ans = Ans * B; ``` 因为矩阵满足结合律，但是不满足交换律。 ## [[HNOI2011]数学作业](https://www.luogu.com.cn/problem/P3216) ### 题目大意 定义一个函数 $G(x)$ 为 $1 \to n$ 的所有数首尾相接。 例如：$G(10) = 12345678910

求 G(n) 在膜 m 意义下的值。

数据范围：1 \le n \le 10^{18}, 1 \le m \le 10^9

题解

假设 f_i 为 G(i) 在膜 p 的值。

那么可以找出初始矩阵 \left[ \begin{matrix} f_i \\ n \\ 1 \end{matrix} \right] 用 \left[ \begin{matrix} 10^k & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix} \right] 取转移即可。

不过这个 k 是当前的位数。

显然上面的柿子不可以直接转移，而且 k 的值域是 18 ，那么我们考虑对于每个 k 取矩阵快速幂就行了。

for(A[0] = i = 1; i <= 18; ++ i) A[i] = A[i - 1] * 10;
for (i = 1; ; ++i) {
    e.a[0][0] = A[i] % p;
    tmp = min(n, A[i] - 1) - A[i - 1] + 1;
    ans = ans * qpow(e, tmp);
    if (A[i] - 1 >= n) break;
}