AT_abc128_f [ABC128F] Frog Jump 题解

· · 题解

最暴力的思路就是枚举 A 和 B，然后统计。复杂为 O(n^2 \log n)。一般来说为了简化计算可以只枚举其中一个端点剩下一个端点可以放在一起计算减少重复计算。这题不太方便这么做，但是思路也是类似的。可以画一下图，模拟一下跳的过程。然后发现 A-B 为一个周期。注意点的分类，奇数步为从终点开始的 A-B 往回眺，偶数步为从起点开始的 A-B 往前跳，于是就可以列出答案式子

\sum\limits_{i=0}^k a_{i \times (A-B)}+a_{n-i \times (A-B)}

发现这次枚举的是 A-B 就可以了，而且这样子每个答案计算式子中就有重合部分了可以前缀和减少重复计算，因为 A 的不同决定了第 k 个周期后跳到终点，于是 k 取任意一个合法的数都可以对答案产生贡献。