ABC415G 矩阵快速幂

· · 题解

先写个暴力 dp，f_i 表示还剩 i 瓶可乐，最大喝完的可乐数。有转移：

f_i=\max\limits_jf_{i-a_j+b_j}+a_j $$f_i=\max\limits_jf_{i-j+mx_j}+j$$ 观察到 $n$ 很大，$m$ 又可以接受三次方，考虑矩阵快速幂。令 $V=300$，维护 $$ \begin{Bmatrix} f_i&f_{i-1}&f_{i-2}&\cdots&f_{i-V+2}&\max\limits_{j=0}^if_i \end{Bmatrix} $$ 这样定义数组 $d$，初始为 $-\infty$： $$d_{i-mx_i-1}\leftarrow\max(d_{i-mx_i-1},i)$$ 有转移： $$ \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\otimes B$ 表示矩阵 $A$ 和 $B$ 的 $(\max,+)$ 广义矩阵乘法。 用矩阵快速幂优化可做到复杂度 $O(V^3\log n)$。 [这是代码。](https://www.luogu.com.cn/paste/tn6rnqqq)