直接贴码了,注释可能有误,欢迎指出
#include<bits/stdc++.h>
using namespace std;/*
注意掉操作过程其实是可逆的
swap有一种方法就是x=x^y y = x^y x = x^y,灵感来源?
所以说其实a,b数组是由基向量生成出来的,如果a数组可以变成b数组,那么他们的基向量得是等价的,既然是等价的必然可以相互转化
所以有了构造思路就是把数组变成同一组0000+基向量的形式
那么答案就是a变成基的正向过程+b变成基的逆向过程details:
(1)对两个不同位置的数操作其实就是把一个数swap到另一个数旁边异或一下,再swap回去
*/
int n;
inline void solve(){cin>>n;vector<int>c(n+1),b(n+1);for(int i = 1;i<=n;++i) cin>>b[i];for(int i = 1;i<=n;++i) cin>>c[i];auto get=[&](vector<int> &a)->vector<pair<int,int>>{vector<int> base(20),pos(20,-1),ff(n+1,-1);//基,基的位置,位置的基(逆映射)vector<pair<int,int>> op;auto swp=[&](int x,int y)->void{op.push_back({x,y});op.push_back({y,x});op.push_back({x,y});};auto insert=[&](int x,int po)->void{for(int i = 15;i>=0;--i){if(!((x>>i)&1)) continue;if(!base[i]){base[i] = x;pos[i]=po;ff[po]=i;break;}else x^=base[i];}};auto XOR=[&](int l,int r)->void{if(l<=r){for(int i = l+1;i<=r-1;++i) swp(i,i-1);op.push_back({r-1,r});for(int i = r-2;i>=l;--i) swp(i,i+1);}else{for(int i = r;i<=l-2;++i) swp(i,i+1);op.push_back({l,l-1});for(int i = l-1;i>r;--i) swp(i,i-1);}};//插入线性基for(int i = 1;i<=n;++i) insert(a[i],i);//将线性基从高位到低位提前int l = 0;//目前基的个数for(int i = 14;i>=0;--i){if(!base[i]) continue;++l;for(int j = pos[i];j>l;--j){if(ff[j]!=-1) pos[ff[j]]=j-1;if(ff[j-1]!=-1) pos[ff[j-1]]=j;swap(ff[j],ff[j-1]);swap(a[j],a[j-1]);swp(j,j-1);}}//构造线性基,类似于高等代数里面的化成阶梯型/*1 1 0 0 1 (1)1 0 1 0 0 (2)0 1 1 1 0 (3)1 0 0 1 0 (4)0 0 0 1 1 (5)先把第一列第一行下面的1全消掉先把第二列第二行下面的1全消掉...*///整个过程是看i这个可以变成基向量元素前面不应该是1的位置把它处理掉for(int i = 1;i<=l;++i){//从高位到低位处理for(int j = 14;j>=0;--j){//从高位到低位处理if(pos[j]==i) break;if(base[j]&&((a[i]>>j)&1)){a[i]^=base[j];XOR(i,pos[j]);}}}//化成最简形式,类似于把阶梯型矩阵化成行最简形式//把第i行第j列上下的1全部消掉,因为已经是阶梯型,所以只有那些基里的1要消了for(int i = 14;i>=0;--i){for(int j = i-1;j>=0;--j){if(base[j]&&(base[i]>>j)&1){a[pos[i]]^=base[j];base[i]^=base[j];XOR(pos[i],pos[j]);}}}//把最前面的L个线性基换到最后面,将后面经过的全部位置变成0for(int i = l,r=0;i>=1;--i,++r){for(int j = i;j<n-r;++j){swp(j,j+1);swap(a[j],a[j+1]);int now = a[j];for(int k = 14;k>=0;--k){if(base[k]&&(now>>k&1)){now^=base[k];if(pos[k]==i){//刚好用的是当前这个异或操作且需要异或a[j]^=base[k];op.push_back({j,j+1});}}}}}return op;};vector<pair<int,int>>op1 = get(b);vector<pair<int,int>>op2 = get(c);reverse(op2.begin(),op2.end());cout<<op1.size()+op2.size()<<"\n";for(auto i:op1) cout<<i.first<<" "<<i.second<<"\n";for(auto i:op2) cout<<i.first<<" "<<i.second<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0;
}