星穹铁道の题解

40pts

直接暴力即可,时间复杂度 O(n^2) 显然无法通过。

100pts

模拟几组数据,容易发现因为 |z_i| \le 1 所以相邻的两个数在经过 x 次变动之后相对位置仍然不会变动,因为每次变动只会增加或者减少1,当相邻的两个数 a_i = a_{i + 1} 的时候他们两个数一定会一起移动(显而易见的 x \equiv x 相同的两个数显然是同余的)

根据这个性质,显而易见的,在 L - R 区间的数原来一定也在 L - R 的区间之中, 所以我们只需要将操作反过来就可以求出原来的数组。时间复杂度 O(n + m)

1 个赞