题解：AT_abc367_d [ABC367D] Pedometer

· · 题解

闲话：赛时切 D 花了 78min，差点比赛结束前都没写完，鉴定为思路对应的代码太难写，输麻了，虽然 rank 3000+ 只掉了 39。

切入正题：首先如果只是求从 1 出发，就是求路径的前缀和，然后看为 0 的个数。（不算 1 本身，共 n-1 个）

以下计算均在模意义下。

但是他要求的是从 1\sim n 每个点出发的答案，如果都这样做就 O(n^2)。

可以发现从 1 到 2，2\sim n 的距离都变近了相同的值（记为 \Delta），可以考虑集体减少记录在 \Delta 中，所以不变；而 2 对应的前缀和被删去了，加入了 1（可直接计算，一整圈的长度减去，由于有集体减少，它需要增加 \Delta 的距离）

于是我们只需要记录绕一整圈的距离、一个 \Delta，处理到 i 时，先去除 i 对应的前缀和，新增一个 i-1 的距离到统计数组中，每次统计 cnt_{\Delta} 即可。

代码链接：https://atcoder.jp/contests/abc367/submissions/56857599