[CF 472F] Design Tutorial: Change the Goal

作法：

這題我是照著官方解寫的，這裡紀錄一下大概作法和證明。

首先就是對給定的陣列和目標陣列做高斯消去，找出這兩個陣列的基底們。假設前者的為$u_1,...,u_x$，後者的則為$v_1,...,v_y$。再來我們需要一個函數把$v_i$以$u$們表示出來，或是回傳無解。也就是我們想要找出$a_1,...,a_x\in \{0,1\}$，使得$\displaystyle \sum_{i=1}^{x} a_i\cdot u_i = w$，其中$w$是一個給定的向量。這也可以透過高斯消去得到解，只要在作完高斯消去時從最後一個變數往前解回去就可以解出所有的$a_i$了（因為此時矩陣已變成了 row echelon form），詳細可以參考 code 。因此就從$v_1$開始，找出他用$u$表示的型式，然後不難把$u_i$們的$u_1$ xor 成$v_1$（因為已經知道他的組成了），並且做完這件事後（不難證明）$u_i$們還會是一組基底。而當我們已經把$u_1,...,u_k$都歸位了（也就是他們分別等於$v_1,...,v_k$時），首先找出$v_{k+1}$對$u_i$們的分解，這時因為我們不能再動到$u_1,...,u_k$，所以如果$u_{k+1}$本身不在$v_{k+1}$的組成中時必須拿$u_{k+2},...,u_x$這些向量的其中一個來和$u_{k+1}$交換，並且滿足這個向量在$v_{k+1}$的組成中。這件事是總是辦的到的，因為如果$v_{k+1}$的組成中沒有任何$u_{k+1},...,u_x$裡的向量，那麼就代表他是由$u_1,...,u_k$組成的，而$u_1,...,u_k$分別等於$v_1,...,v_k$，也就代表$v_1,...,v_k$可以組成$v_{k+1}$，和$v$是一組基底矛盾，因此這樣做不會有問題。最後還要注意到的是，如果$y<x$，那麼要記得把$u_{x+1},...,u_y$全部都自己 xor 自己變成$0$，才會和目標陣列高斯消去後的結果一樣。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int maxn=10000+10 ;
 
int gauss_elim(int *t,int n,vector<pii> &v)
{
    v.clear() ;
    int j=0 ;
    for(int i=0;i<31;i++)
    {
        int x=-1 ;
        for(int k=j;k<n;k++) if(t[k]&(1<<i))
            {x=k ; break ;}
        if(x==-1) continue ;
        if(x!=j)
        {
            swap(t[x],t[j]) ;
            v.push_back(pii(x,j)) ;
            v.push_back(pii(j,x)) ;
            v.push_back(pii(x,j)) ;
        }
        for(int k=j+1;k<n;k++) if(t[k]&(1<<i))
            v.push_back(pii(k,j)) ,
            t[k]^=t[j] ;
        j++ ;
    }
    return j ;
}
 
int tmp[50],tmp2[50] ;
bool decomp(int *t,int n,int val,int *res)
{
    memset(tmp2,0,sizeof(tmp2)) ;
    for(int i=0;i<n;i++) for(int j=0;j<30;j++)
        if(t[i]&(1<<j)) tmp2[j]|=(1<<i) ;
    for(int j=0;j<30;j++) if(val&(1<<j))
        tmp2[j]|=(1<<n) ;
    vector<pii> nouse ;
    gauss_elim(tmp2,30,nouse) ;
 
    fill(res,res+n,0) ;
    for(int i=29;i>=0;i--) if(tmp2[i])
    {
        if(tmp2[i]==(1<<n)) return 0 ;
        int j=0 ;
        while(!(tmp2[i]&(1<<j))) j++ ;
        res[j]=(tmp2[i]&(1<<n)) ? 1 : 0 ;
        for(int k=j+1;k<n;k++) if(tmp2[i]&(1<<k))
            res[j]^=res[k] ;
    }
    return 1 ;
}
 
int a[maxn],b[maxn] ;
vector<pii> v1,v2 ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<n;i++) scanf("%d",&a[i]) ;
    for(int i=0;i<n;i++) scanf("%d",&b[i]) ;
    int x=gauss_elim(a,n,v1) ;
    int y=gauss_elim(b,n,v2) ;
 
    reverse(v2.begin(),v2.end()) ;
    for(int i=0;i<y;i++)
    {
        if(!decomp(a,x,b[i],tmp))
            {printf("-1\n") ; return 0 ;}
        if(!tmp[i]) for(int j=i+1;j<x;j++) if(tmp[j])
        {
            swap(tmp[i],tmp[j]) ;
            swap(a[i],a[j]) ;
            v1.push_back(pii(i,j)) ;
            v1.push_back(pii(j,i)) ;
            v1.push_back(pii(i,j)) ;
        }
        tmp[i]=0 ;
        for(int j=0;j<x;j++) if(tmp[j])
            v1.push_back(pii(i,j)) ,
            a[i]^=a[j] ;
    }
    for(int i=y;i<x;i++) v1.push_back(pii(i,i)) ;
    printf("%d\n",v1.size()+v2.size()) ;
    for(auto i : v1) printf("%d %d\n",i.first+1,i.second+1) ;
    for(auto i : v2) printf("%d %d\n",i.first+1,i.second+1) ;
}