CF889E Mod Mod Mod 题解

首先我们有一个倒着 DP 的做法就是你维护 $f_{i,j}$ 表示 $i$ 之前的取模不生效的情况下，$X<j$ 的答案。

转移找到首个 $a_k<j$ 的 $k$，令 $c=\lfloor j/a_k \rfloor$，有 $f_{i,j}=\max(f_{k,a_k}+a_k(c-1)(k-1),f_{k,j\bmod a_k}+a_kc(k-1))$，这么转移是因为 $<j$ 的数中只有最大的 $a_k$ 个数有用，分为最大的 $j\bmod a_k$ 个数和去掉余数后最大的 $a_k$ 个数转移。

这里有用的状态显然只有每个点出发取模的断点（对于每个 $i$ 求 $a_i \bmod a_{i+1}\bmod a_{i+2}\dots \bmod a_n$ 中 $a_i$ 发生变化的位置），共 $O(n\log V)$ 个。容易用 P11692 求出所有状态然后直接转移。

时空复杂度 $O(n\log V)$，空间不能通过，我感觉时间也不能过。