CF1748F Solution

link

题目也就是要我们交换每对 \(a_i\) 和 \(a_{n-1-i}\)。考虑如何利用这个异或操作交换：我们自然地想到 x^=y,y^=x,x^=y。

如何操作使得 x^=y？我们把环上 \(x\) 到 \(y\) 的路径拉出来，假装是个序列：

\(a_x.a_{x+1},a_{x+2},\dots,a_{y-2},a_{y-1},a_y\)

现在要使 \(a_x\) 异或上 \(a_y\)，进行以下操作：

• 从 \(y-1\) 到 \(x\) 顺次操作一下。这样每个数就变成了原先 \(a\) 的异或后缀和。

• 从 \(x+1\) 到 \(y-1\) 顺次操作一下。这样把除了 \(x\) 的数复原回去了，除了 \(a_x\) 仍是 \(x\dots y\) 的异或和。

• 从 \(y-2\) 到 \(x\) 顺次操作一下。这样每个数又变成了原先 \(a\) 的异或后缀和，只不过尾巴是 \(y-1\)。\(a_x\) 在进行完这次操作后就异或上了 \(a_y\)。

• 最后类似的，从 \(x+1\) 到 \(y-2\) 顺次操作一下。于是把这些数都复原回去了。

如果 \(x\) 到 \(y\) 的距离是 \(d\)，使 \(a_x\) 异或上 \(a_y\) 大概要用 \(4d\) 次操作。

每次交换要进行三次上述操作。考虑交换 \(a_i,a_{n-1-i}\)，注意距离是有顺序的，如果 x^=y 走短的边，y^=x 走长边，

操作数大概是 \(2\sum_{i=1}^{n/4}4(2i+n-2i+2i)=2.5n^2+2n\)，过不去。

考虑在进行 \(i,n-1-i(i < n/4)\) 的异或操作时，第三步完成后恰好完成了 \(i-1,n-i\) 的异或操作的第一步。那么每次异或操作的次数就可以降到 \(2d\)（省去了第一次和第四次）。

操作数大概是 \(2\sum_{i=1}^{n/4}2(2i+n-2i+2i)=1.25n^2+n\)，可以通过。