Description

There are two sequences({Ai},{Bi}) of length N.
Your goal is to minimize the times of operations that turning A into B.You can repeatly perform the following operations：
1.Let the XOR of all elements in A be X
2.Replace a arbitrary element in A with X
 Especially,if it is impossible to turn A into B,output “-1”
 N<=10^5,Ai,Bi<=2^30
 

Analysis

let a[0] be a[1] xor a[2] xor …. xor a[n],and so as b[0],and then it is simple to judge -1
the operation equal to swap a[0] and a[i]
After considering some simple cases,we notice that the procedure corresponds permutations,which mind us using graph to solve it.
Conclusion:If the connected component(including k vertex) including a[0],then ans+=k else ans+=k+1
Obviously if a[i]=b[i] we will never change it,else we link an edge from a[i] to b[i].
Since the in-degree equals to the out-degree for any vertex,every component constitute a Eulerian circuit.So we prove the conclusion above.
Now the problem is simple:Only need to count the number of connected component in the graph by union-find sets.

最后

以上就是冷艳蜡烛最近收集整理的关于【AGC 016 D】XOR ReplaceDescriptionAnalysis的全部内容，更多相关【AGC内容请搜索靠谱客的其他文章。