动态规划——矩阵优化DP 学习笔记
前置知识:矩阵、矩阵乘法。
矩阵乘法优化线性递推
斐波那契数列
在斐波那契数列当中,(f_1 = f_2 = 1),(f_i = f_{i – 1} + f_{i – 2}),求 (f_n)。
而分析式子可以知道,求 (f_k) 仅与 (f_{k – 1}) 和 (f_{k – 2}) 有关;
所以我们设矩阵 (F_i = begin{bmatrix} f_{i – 1} & f_{i – 2} end{bmatrix})。
设矩阵 (text{Base}),使得 (F_{i – 1} times text{Base} = F_i),接下来考虑 (text{Base}) 是什么;
带入可得 (begin{bmatrix} f_{i – 2} & f_{i – 3} end{bmatrix} times text{Base} = begin{bmatrix} f_{i – 1} & f_{i – 2} end{bmatrix})。
即 (begin{bmatrix} f_{i – 2} & f_{i – 3} end{bmatrix} times text{Base} = begin{bmatrix} f_{i – 2} + f_{i – 3} & f_{i – 2} end{bmatrix});
根据矩阵乘法的规则可知 (text{Base}) 的第 (1) 列应为 (begin{bmatrix} 1 & 1 end{bmatrix}^text{T}),第 (2) 列应为 (begin{bmatrix} 1 & 0 end{bmatrix}^text{T})。
所以求得 (text{Base} = begin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix})。
然后考虑 (f_i) 的值应该是多少;
根据前面的公式可以知道 (f_i = F_{n + 1}) 的第一个数,所以就是求这个数。
根据 (f_1 = f_2 = 1),可以知道 (F_3 = begin{bmatrix} f_2 & f_1 end{bmatrix} = begin{bmatrix} 1 & 1 end{bmatrix}),我们将这个作为边界值;
然后有 (F_4 = F_3 times text{Base}),(F_5 = F_4 times text{Base} = F_3 times text{Base} times text{Base})。
因为矩阵乘法有结合律,所以 (F_{n + 1} = F_3 times text{Base}^{n – 2} = begin{bmatrix} 1 & 1 end{bmatrix} times begin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix}^{n – 2})。
因为矩阵没有交换律,所以 (F_3)(前)和 (text{Base}^{n – 2})(后)一定不能写反了!
例题1
(left{begin{array}{l}
f_1 = f_2 = 0 \
f_i = f_{i – 1} + f_{i – 2} + 1
end{array}right.)
点击查看题解
(f_i) 仅与 (f_{i – 1}) 和 (f_{i – 2}) 有关,同时还包括了常数 (1),
所以我们设 (F_i = begin{bmatrix} f_{i – 1} & f_{i – 2} & 1 end{bmatrix}),
然后设 (text{Base}) 使得 (F_{i – 1} times text{Base} = F_i),
即 (begin{bmatrix} f_{i – 2} & f_{i – 3} & 1 end{bmatrix} times text{Base} = begin{bmatrix} f_{i – 1} & f_{i – 2} & 1 end{bmatrix})。
因为 (f_{i – 1} = f_{i – 2} + f_{i – 3} + 1),所以易知:
(text{Base} = begin{bmatrix} 1 & 1 & 0 \ 1 & 0 & 0 \ 1 & 0 & 1 end{bmatrix}).
边界条件为 (F_3 = begin{bmatrix} 0 & 0 & 1end{bmatrix}),
所以 (F_{n + 1} = F_3 times text{Base}^{n – 2})。
即可求出 (f_n).
例题2
(left{begin{array}{l}
f_1 = 0 text{,} f_2 = 1 \
f_i = f_{i – 1} + f_{i – 2} + i
end{array}right.)
点击查看题解
(f_i) 仅与 (f_{i – 1})、(f_{i – 2}) 和 (i) 有关,为实现 (i) 的递增,还需设置常量 (1);
所以我们设 (F_i = begin{bmatrix} f_{i – 1} & f_{i – 2} & i & 1 end{bmatrix}),
由 (F_{i – 1} times text{Base} = F_i) 得 (text{Base} = begin{bmatrix} 1 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 \ 1 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 end{bmatrix}).
边界条件为 (F_3 = begin{bmatrix} 1 & 0 & 3 & 1 end{bmatrix}).
(F_{n + 1} = F_3 times text{Base}^{n – 2});即可求出 (f_n)。
例题3(来自 OI-Wiki)
(left{begin{array}{l}
f_{1} = f_{2} = 0 \
f_{n} = 7f_{n-1}+6f_{n-2}+5n+4times 3^n
end{array}right.)
点击查看题解
我的解法与 OI-Wiki 上的有所不同:
设 (F_n = begin{bmatrix} f_{n – 1} & f_{n – 2} & n & 3^n & 1 end{bmatrix}).
易知 (text{Base} = begin{bmatrix} 7 & 1 & 0 & 0 & 0 \ 6 & 0 & 0 & 0 & 0 \ 5 & 0 & 1 & 0 & 0 \ 4 & 0 & 0 & 3 & 0 \ 0 & 0 & 1 & 0 & 1 end{bmatrix}).
边界值 (F_3 = begin{bmatrix} 0 & 0 & 3 & 27 & 1 end{bmatrix}).
则 (F_{n + 1} = F_3 times text{Base}^{n – 2}).
例题4
(left{begin{array}{l}
f_1 = f_2 = 0 text{,} f_3 = 1 \
f_i = 3f_{i – 1} + 2f_{i – 2} + f_{i – 3} + 5i + 7
end{array}right.)
点击查看题解
增加了 (f_{i – 3}),但是本质是一样的。
可以设 (F_i = begin{bmatrix} f_{i – 1} & f_{i – 2} & f_{i – 3} & i & 1 end{bmatrix}),
易得 (text{Base} = begin{bmatrix} 3 & 1 & 0 & 0 & 0 \ 2 & 0 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 \ 5 & 0 & 0 & 1 & 0 \ 7 & 0 & 0 & 1 & 1 end{bmatrix}).
而 (F_4 = begin{bmatrix} 1 & 0 & 0 & 4 & 1 end{bmatrix}),
则 (F_{n + 1} = F_4 times text{Base}^{n – 3})。
例题5
洛谷 P1939 矩阵加速(数列):https://www.luogu.com.cn/problem/P1939
考虑这道题 (text{Base}) 该如何设置。
点击查看代码
#include
#define rr read()
using namespace std;
const long long MOD = 1e9 + 7;
inline int read()
{
int num = 0, flag = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
flag = -1;
for (; isdigit(ch); ch = getchar())
num = (num >= 1, Base = Base * Base;
}
printf("%lldn", (res.a[1][1] + res.a[2][1] + res.a[3][1]) % MOD);
}
return 0;
}
时间复杂度
矩阵乘法 (O(k^3)) 其中 (k) 为矩阵的长(或宽);
快速幂 (O(log n));
所以[矩阵乘法优化线性递推]的时间复杂度为 (O(k^3 log n))。
矩阵乘法优化 DP
朴素矩阵乘法
有 (mathrm{dp}[t][x][y] = sumlimits_{w = 1}^n mathrm{dp}[t][x][w] times G[w][y]),
则可以看为矩阵乘法的形式:(mathrm{dp}_t = mathrm{dp}_{t – 1} times G),即 (mathrm{dp}_t = Ans_0 times G^t)。
广义矩阵乘法
考虑将原公式推广,即广义矩阵乘法:对于矩阵 (A_{n times m}) 和 (B_{m times r}):
有 (C_{ij} = A times B = bigopluslimits_{k = 1}^m , (A_{ik} otimes B_{kj})),我们将其成为 ((otimes, ; oplus)) 的矩阵乘法。
当满足以下条件时,广义矩阵乘法满足结合律:
- (otimes) 具有结合律和交换律;
- (otimes) 对 (oplus) 存在分配律,即满足 ((a oplus b) otimes c = (a otimes c) oplus (b otimes c))。
常见的矩阵乘法形式有 ((pm, ; max))、((pm, ; min))、((land, ; lor))。
然后对矩阵的乘法重载为此解法即可用快速幂求解了,具体的可以看这篇文章:https://www.luogu.com.cn/blog/i207M/xie-ti-bao-gao-sp1716-gss3-can-you-answer-these-queries-iii。
多组询问的矩阵乘法优化 DP
例题:P6569 魔法值
我们要求一个 (mathrm{Ans}_k = mathrm{Ans}_0 times mathrm{Mp}^k),其中 (mathrm{Ans}_i) 是一个长度为 (n) 的行向量。
那么,我们先预处理 (mathrm{Mp}^k),即 (mathrm{Mp}^{2^i})。
然后我们就是在求一个行向量和 (log_2 k) 个 (n times n) 的矩阵的乘积了。
在算答案的时候,我们先别算这 (log_2 k) 个方阵的乘积,先用 (mathrm{Ans}_0) 向量从左乘到右。
因为向量乘矩阵复杂度是 (O(n^2)) 的!
这样复杂度就从 (O(q times n^3 log_2 t)),变成了 (O(n^3 log_2 t+q times n^2 log_2 t))。
练习题
见:https://www.luogu.com.cn/training/385249
Reference
[1] https://oi-wiki.org/math/linear-algebra/matrix/
[2] https://www.cnblogs.com/ningago/p/17472070.html
[3] https://www.cnblogs.com/luckyblock/p/14430820.html
[4] http://blog.tsawke.com/Data/Blog/content/DDP.html
[5] https://blog.csdn.net/qq_41739081/article/details/128184363
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net