More precisely, the bitwise exclusive-OR operation is a binary operation which is equivalent to applying logical exclusive-OR to every pair of bits located on the same positions in binary notation of operands. In other words, a binary digit of the result is equal to. 1 if and only if bits on the respective positions in the operands are different. For example, if. Now AAA wants to find out the minimum sum of all the elements in the sequence, or determine that the sequence meets all the constraints does not exist.
AAA has a nonnegative integer sequence a_1,a_2,ldots,a_n a 1 ,a 2 ,…,a n with m m constraints, each of which is described as a_u oplus a_v = w a u ⊕a v =w, where oplus ⊕ denotes the bitwise exclusive-OR operation. More precisely, the bitwise exclusive-OR operation is a binary operation which is equivalent to applying logical exclusive-OR to every pair of bits located on the same positions in binary notation of operands. In other words, a binary digit of the result is equal to 1 1 if and only if bits on the respective positions in the operands are different. For example, if X = 109_{10} = 1101101_{2} X=109 10 =1101101 2 and Y = 41_{10} = 101001_{2} Y=41 10 =101001 2 , then X oplus Y = 1000100_{2} = 68_{10} X⊕Y=1000100 2 =68 10 . Now AAA wants to find out the minimum sum of all the elements in the sequence, or determine that the sequence meets all the constraints does not exist.
标签: HBC230851[HAOI2007]反素数ANT 深度优先搜索(DFS) 数学 贪心 数论 搜索 搜索Bitwise Exclusive-OR Sequence题解