[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;
}