什么是矩乘
一些好题
这里没什么板题，都是些比较妙的矩乘，逐步深入。
这是一个蒟蒻的刷题历程，大佬轻喷。
这里面的题目都没放代码，因为矩阵的代码一定要自己写一遍，每个人的都不一样的。
[NOI2012]随机数生成器
题目大意
给你很多数字：\(\text{m, a, c, x0 n, g}\) 和一个递推式：
要你求 \(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\) ):
这个每次转移是互不影响的,所以可以矩乘,然后就是一样的操作了.
这还是不能过!!!因为你 \(u,v\) 是可以达到 \(1000\) 的,所以你还要离散化.
[TJOI2017]可乐
题目大意
\(0\) 时刻，你从 \(1\) 号节点出发，问你 \(t\) 时刻他行走的方案数，每次他可以停在原地，移动到相邻的节点，自爆。
数据范围： \(n,m \le 100, t \le 10 ^ 9\)
题解
考虑先枚举时间，每次可以简单的 \(dp\) 一下。
那么我们肯定不可以留下一个 \(t\) 的复杂度，但是你看 \(n\) 的数据范围，这一看就很矩乘。
那就矩乘呗，和上个题一样，不过唯一要注意的是自爆操作，这个操作只要把每个点向 \(0\) 连一条边就行了，\(0\) 没有任何出度。
[NOI2013]矩阵游戏
题目大意
给你 \(a, b, c, d, n, m\)
要你求满足以下递推式的 \(f_{n,m}\) 是多少。
数据范围： \(1 \le n, m \le 10^{1000000}, 1 \le a, b, c, d \le 10^9\)
题解
\(n, m\) 这么大，而且这个矩阵这么具有矩阵性，那就矩乘了呗。。
我们把 \(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\) 次。
但是不可以直接那么做，需要：
A = qpow(A, m - 1), B = qpow(A * B, n - 1) * A;
Ans = Ans * B;
因为矩阵满足结合律，但是不满***换律。
[HNOI2011]数学作业
题目大意
定义一个函数 \(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;
}
京公网安备 11010502036488号