题解：CF1748F Circular Xor Reversal

潘德理2010 · 2026-08-10 16:18:01 · 题解

考虑一种基础操作，交换。而交换相当于三次异或，即 a^=b,b^=a,a^=b。考虑如何实现令 a_i 变为 a_i \operatorname{xor} a_j。不难想到以下方式，记为 f(i,j)：

1. 从 j-1 到 i 依次执行操作。

2. 从 i+1 到 j-1 依次执行操作。

3. 从 j-2 到 i 依次执行操作。

4. 从 i+1 到 j-2 依次执行操作。

总共使用 4(j-i) 步交换两个数。按照这种方法，将需要 3n^2 步，无法通过。考虑优化。

手玩一下即可发现 f(i,j) 的第四步和 f(i+1,j-1) 的第一步相同，可以互相抵消。这样的话第一步和第四步都没了，总步数少一半，为 1.5n^2，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=405;
int n;
vector<int> ans;
void ins(int x){
    ans.push_back(x%n);
}
void sol(int l,int r){
    for(int i=r-1;i>=l;i--) ins(i);
    while(l<r){
        for(int i=l+1;i<=r-1;i++) ins(i);
        for(int i=r-2;i>=l;i--) ins(i);
        l++,r--;
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    sol(0,n-1);
    int d=(n-1)/2;
    if(n&1) sol(d+1,n+d-1);
    else sol(d+1,n+d);
    sol(0,n-1);
    cout<<(int)ans.size()<<"\n";
    for(int i:ans){
        cout<<i<<" ";
    }
}