专栏文章

ABC415G 矩阵快速幂

rran_qwq
AT_abc415_g题解参与者 7已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miotyytz
此快照首次捕获于
2025/12/03 01:07
3 个月前
此快照最后确认于
2025/12/03 01:07
3 个月前
查看原文
先写个暴力 dp，fif_i 表示还剩 ii 瓶可乐，最大喝完的可乐数。有转移：
fi=max⁡jfi−aj+bj+ajf_i=\max\limits_jf_{i-a_j+b_j}+a_j
mm 有 2×1052\times 10^5，但对于同一个 aia_i，只会取到 bib_i 最大的。设 mximx_i 为 aj=ia_j=i 最大的 bjb_j，转移可以改写：
fi=max⁡jfi−j+mxj+jf_i=\max\limits_jf_{i-j+mx_j}+j
观察到 nn 很大，mm 又可以接受三次方，考虑矩阵快速幂。令 V=300V=300，维护
{fifi−1fi−2⋯fi−V+2max⁡j=0ifi}\begin{Bmatrix} f_i&f_{i-1}&f_{i-2}&\cdots&f_{i-V+2}&\max\limits_{j=0}^if_i \end{Bmatrix}
这样定义数组 dd，初始为 −∞-\infty：
di−mxi−1←max⁡(di−mxi−1,i)d_{i-mx_i-1}\leftarrow\max(d_{i-mx_i-1},i)
有转移：
{fi−1fi−2fi−3⋯fi−V+1max⁡j=0i−1fi}⊗{d00−∞⋯−∞d0d1−∞0⋯−∞d1d2−∞−∞⋯−∞d2⋮⋮⋮⋱⋮⋮dV−2−∞−∞⋯−∞dV−2−∞−∞−∞⋯−∞0}={fifi−1fi−2⋯fi−V+2max⁡j=0ifi}\begin{Bmatrix} f_{i-1}&f_{i-2}&f_{i-3}&\cdots&f_{i-V+1}&\max\limits_{j=0}^{i-1}f_i \end{Bmatrix} \otimes \begin{Bmatrix} d_0&0&-\infty&\cdots&-\infty&d_0\\ d_1&-\infty&0&\cdots&-\infty&d_1\\ d_2&-\infty&-\infty&\cdots&-\infty&d_2\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ d_{V-2}&-\infty&-\infty&\cdots&-\infty&d_{V-2}\\ -\infty&-\infty&-\infty&\cdots&-\infty&0 \end{Bmatrix} = \begin{Bmatrix} f_i&f_{i-1}&f_{i-2}&\cdots&f_{i-V+2}&\max\limits_{j=0}^if_i \end{Bmatrix}
其中 A⊗BA\otimes B 表示矩阵 AA 和 BB 的 (max⁡,+)(\max,+) 广义矩阵乘法。
用矩阵快速幂优化可做到复杂度 O(V3log⁡n)O(V^3\log n)。
这是代码。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...