[AGC016D] XOR Replace

[AGC016D] XOR Replace

观察操作的性质，记长度为 \(n+1\) 的序列 \(c\) 满足：

\[c_i = \begin{cases} a_i & i \leq n \\ a_1 \oplus a_2 \oplus \dots \oplus a_n & i = n + 1 \end{cases} \]

则每次操作相当于选择 \(i \in [1,n]\)，交换 \(c_i\) 和 \(c_{n+1}\)。

我们要使 \(c\) 的前 \(n\) 个数与 \(b\) 相同，发现 \(c\) 可以任意交换，于是我们便可以判无解。

异或的性质用完了，接下来我们考虑图论建模刻画这个过程。

首先对于 \(c_i = b_i\)，我们可以不用管。

接下来考虑对剩下的 \((c_i,b_i)\) 连边，分两种情况考虑。

首先是 \(c_{n+1}\) 无连边的情况，此时每个点的度数必然是偶数。

每个连通块都存在一条欧拉回路，考虑对于欧拉回路如何操作。

我们对于路径 \(u_1 \to u_2 \to \dots \to u_m \to u_1\)，采取如下过程：

• 交换 \(u_1\) 和 \(c_{n+1}\)

• 交换 \(u_2\) 和 \(c_{n+1}\)

• \(\dots\)

• 交换 \(u_n\) 和 \(c_{n+1}\)

• 交换 \(u_1\) 和 \(c_{n+1}\)

此时的答案是边数与连通块个数之和。这里的连通块不计孤立点，因为孤立点无需考虑。

接下来考虑 \(c_{n+1}\) 有连边的情况，此时会将欧拉回路拆成欧拉路径，答案可以 \(-1\)。

//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
int a[100010],b[100010];
map<int,vector<int> > G;
map<int,bool> vis;
void dfs(int u){
	vis[u]=true;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(!vis[v]){
			dfs(v);
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[n+1]^=a[i];
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	map<int,int> dict;
	for(int i=1;i<=n+1;i++){
		dict[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		dict[b[i]]--;
		if(dict[b[i]]<0){
			printf("-1");
			return 0;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=b[i]){
			ans++;
			G[a[i]].push_back(b[i]);
			G[b[i]].push_back(a[i]);
		}
	}
	for(map<int,vector<int> > :: iterator iter=G.begin();iter!=G.end();iter++){
		int u=iter->first;
		vector<int> vec=iter->second;
		if(!vis[u]  &&  !vec.empty()){
			ans++; 
			dfs(u);
		}
	}
	if(!G[a[n+1]].empty()){
		ans--;
	}
	printf("%d",ans);
	return 0;
}