题解：CF2145F Long Journey

注意到 $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)$ 可过。