题解

思路

按移动次数分层。设上一层 prev[s] 表示恰好完成若干次移动后到达 $s$ 的方案数；当前移动的基数为 $d$，则

每层的 cur 都应累加到最终答案。

做法

小规模递归枚举每次移动的正倍数。中规模直接枚举 $q$ 完成上述转移。满分利用同余类前缀和：$cur[s]=prev[s-d]+cur[s-d]$。最小总移动长度 $k+(k+1)+\cdots$ 很快超过 $n$，有效层数为 $O(\sqrt n)$。

复杂度

满分时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n)$；中规模直接转移为 $O(n^2\log n)$ 的上界。

正确性证明

第 $j$ 次移动长度唯一表示为正整数倍 $q(k+j-1)$，因此转移逐一枚举了上一层方案的所有合法延伸，且不同的 $q$ 不重复。递推式按同余类维护同一求和，和直接转移等价。将每个移动次数层累加后，恰好统计所有允许的正移动次数，故答案正确。