[Test-1.11]-T4 Transform

Description:

对于一个序列 \({a_n}\)，定义操作 (x, y)，它的意义是：\(a_x\) ← \(a_x\) xor \(a_y\)。
给定一个初始序列 \({a_n}\) 和一个目标序列 \({b_n}\)，你需要对 \({a_n}\) 进行若
干次操作，使它变为 \({b_n}\)。
试构造一组操作数 ≤ 1e6 的合法操作序列。

Input:

第一行一个整数 \(n\)。
第二行 \(n\) 个整数，表示 \({a_n}\)。
第三行 \(n\) 个整数，表示 \({b_n}\)。

Output:

若无解，输出一行 -1。
否则第一行输出操作数 tot，接下来 tot 行每行两个整数 x, y，描述一
个操作。

Constraints：

n ≤ 1e4, \({a_i}\) ≤ 2 × 1e9

Solution:

注意这个操作很像求线性基时候去配线性基
我们可以求出\({A_n}\)的线性基
如果用\({A_n}\)的线性基直接凑\({B_n}\)的话原来的可能某维的基被拿到别的维去了
可以考虑同时求出\({B_n}\)的线性基，然后用\({A_n}\)的线性基凑\({B_n}\)的线性基，因为求线性基的操作是可逆的，
所以我们在做的时候记录一下怎么到这里来的就行。

Code:

#include<iostream>
#include<cstdio>
#include<vector>
#define R register
namespace OO
{
    const int ios = (1<<17);
    char RR[ios], *Rc = RR, *Rb = RR;
    char gec(){return ((Rc==Rb&&(Rb=(Rc=RR)+fread(RR,1,ios,stdin),Rc==Rb))?EOF:*Rc++);}
    template<class T>
    void rea(T &x)
    {
        char ch=gec();int f(0);x = 0;
        while(!isdigit(ch)){f|=ch=='-';ch=gec();}
        while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gec();}
        x = f?-x:x;
    }
    void reas(char*cur)
    {
        char ch=gec();
        while(isspace(ch)&&ch!=EOF) ch=gec();
        if(ch==EOF) return;
        while(!isspace(ch)) (*cur++)=ch,ch=gec();
        *cur = 0;
    }
    template<class T>
    T max(T a, T b) {return (a>b?a:b);}
    template<class T>
    T min(T a, T b) {return (a<b?a:b);}
}
using OO::gec;using OO::rea;using OO::reas;
using namespace std;
int n, a[10005], b[10005], c[1005], p;
typedef pair<int, int> P;
vector<P>A, B;
void Xor(int *o, vector<P> &v, int x ,int y) {o[x] ^= o[y]; v.push_back(make_pair(x, y));}
void guass(int *x, vector<P> &v)
{
    p = 1;
    for(R int i = 30; i >= 0; --i)
    {
        for(R int j = p; j <= n; ++j) if(x[j]>>i&1)
        {
            if(j == p) break;
            Xor(x, v, p, j), Xor(x, v, j, p), Xor(x, v, p, j);
            break;
        }
        if(!(x[p]>>i&1)) continue;
        for(R int j = p+1; j <= n; ++j) if(j != p)
            if(x[j]>>i&1) Xor(x, v, j, p);
        c[p] = i; p++;
    }
}
int main()
{
    freopen("transform.in","r",stdin);
    freopen("transform.out","w",stdout);
    using OO::max;using OO::min;
    rea(n);
    for(R int i = 1; i <= n; ++i) rea(a[i]);
    for(R int i = 1; i <= n; ++i) rea(b[i]);
    guass(b, B); guass(a, A);
    for(R int i = 1; i <= p; ++i)
        for(R int j = i; j <= p; ++j)
            if(((a[i]^b[i])>>c[j])&1) Xor(a, A, i, j);
    for(R int i = 1; i <= p; ++i) if(a[i] != b[i]) return puts("-1"), 0;
    printf("%d\n", A.size()+B.size());
    for(R int i = 0; i < A.size(); ++i) printf("%d %d\n", A[i].first, A[i].second);
    for(R int i = B.size()-1; i >= 0; --i) printf("%d %d\n", B[i].first, B[i].second);
    return 0;
}