题解：CF2145F Long Journey
xzy090626
·
·
题解
这个题，800 吧。
注意到 L=\operatorname{LCM}_{i=1}^n a_i 一定可以作为格子的循环节，即第 i 个格子与第 i+L 个格子的状态任意情况下都相同。因此我们可以将格子的数量从 O(m) 缩到 O(L) 级别。
现在考虑时间上的循环，由于时间上的循环节长度为 n，因此本质不同的时空状态只有 O(nL) 种。不妨直接对于每种状态通过倍增向右转移，转移策略显然是能往右走就往右走。
设 f_{i,j,k} 为当前在满足 pos\bmod L=i 的 pos 的位置，且时间为 t 满足 t\bmod n = j，走 2^k 轮能走到哪里（以上默认下标从 0 开始）。这个状态的好处是状态容易转移，而如果设成走的距离对应时间的话可能不太方便（？
于是转移就是 \displaystyle{f_{i,j,k}=f_{i,j,k-1}+f_{(i+f_{i,j,k-1})\bmod L,j+2^{k-1},k-1}}。
查询的时候直接从大到小枚举 2^k，能走就走。总时间复杂度是 O(TnL\log m) 可过。