[学习笔记] 倍增 Floyd
一、朴素 Floyd
for (int i = 1;i <= n; ++ i) {
for (int j = 1;j <= n; ++ j) {
for (int k = 1;k <= n; ++ k) {
d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
}
}
}
二、倍增 Floyd / 传递闭包
要做 \(k(\leq 10^9)\) 次 Floyd，怎么办？
将 Floyd 转化为广义矩阵乘法，直接跑矩阵快速幂，可以优化到 \(O(n^3\log k)\)。
三、P2886 Cow Relays G
首先先离散化，因为边数有 \(100\) 条所以点数最多 \(200\) 个。
传递闭包：先将初始临界矩阵 \(M\) 建立出来，\(M^k\) 就代表经过 \(k\) 条边的最短路；将其设为 \(0/1\)（有无边）可以求出任意两点之间的路径数。
四、P6569 [NOI Online #3 提高组] 魔法值
朴素的 40pts 做法：
第 \(i\) 天的魔法值的对应矩阵：
\[Mt_i=\begin{bmatrix}f_{1,i}&f_{2,i}&\dots&f_{n-1,i}&f_{n,i}\end{bmatrix}
\]
转移方程，设 \(S_u\) 表示与 \(u\) 相邻的城市：
\[f_{u,i}=\bigoplus_{v \in S_u}f_{v,i-1}
\]
设 \(T_{u,v}\) 表示 \(u\) 与 \(v\) 是否连通。
重载矩阵乘法：
\[A\times B=C
\]
\[C_{i,j}=\bigoplus_{k=1}^{n}A_{i,k}B_{k,j}
\]
转移矩阵：
\[M=\begin{bmatrix}T_{1,1}&T_{1,2}&\cdots&T_{1,n-1}&T_{1,n}\\T_{2,1}&T_{2,2}&\cdots&T_{2,n-1}&T_{2,n}\\\vdots&\vdots&\ddots&\vdots&\vdots\\T_{n-1,1}&T_{n-1,2}&\cdots&T_{n-1,n-1}&T_{n-1,n}\\T_{n,1}&T_{n,2}&\cdots&T_{n,n-1}&T_{n,n}\end{bmatrix}
\]
\[Mt_{k}=Mt_{k-1}\times M
\]
\[Mt_{k}=M t_0\times M^k
\]
卡常后的 100pts 做法：
你还需要：亿点点信仰！&& O2 优化
- 矩阵乘法交换顺序，如：
matrix operator * (matrix A, matrix B) {
matrix C;
if (A.m == B.n) ; else swap (A, B);
C.n = A.n, C.m = B.m;
rep (i, 1, C.n) rep (j, 1, C.m) C.a[i][j] = 0;
rep (i, 1, C.n) {
rep (k, 1, A.m) {
rep (j, 1, C.m) {
C.a[i][j] ^= B.a[k][j] * A.a[i][k];
}
}
}
return C;
}
- 预处理矩阵的 \(2\) 次方幂：
thxy[0] = M;
rep (i, 1, 32) thxy[i] = thxy[i - 1] * thxy[i - 1];
- 使用位运算计算：
for (int j = 1, _ = 0; j <= ai; j <<= 1, ++ _) {
if ((ai & j)) mxp = flag ? mxp * thxy[_] : thxy[_], flag |= 1;
}