#PU1518. USACO 2025 US Open Contest, Silver — Problem 1. Sequence Construction
USACO 2025 US Open Contest, Silver — Problem 1. Sequence Construction
USACO 2025 US Open Contest, Silver — Problem 1. Sequence Construction
题目描述
Lately, the cows on Farmer John's farm have been infatuated with watching the show Apothecowry Dairies. The show revolves around a clever bovine sleuth CowCow solving problems of various kinds. Bessie found a new problem from the show, but the solution won't be revealed until the next episode in a week! Please solve the problem for her. You are given integers and . Please choose a positive integer and construct a sequence of non-negative integers such that the following conditions are satisfied: $\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K$ If no such sequence exists, print . is the number of bits equal to in the binary representation of the integer . For instance, the popcount of is and the popcount of is . is the bitwise xor operator. The input will consist of () independent test cases.
输入格式
The first line contains . The first and only line of each test case has and . It is guaranteed that all test cases are unique.
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
2 1
33 5
10 5
2
2 0
3
3 23 7
-1
In the first test case, the elements in the array $a = [2, 0]$ sum to $2$. The
xor sum of popcounts is $1 \oplus 0 = 1$. Thus, all the conditions are
satisfied.
In the second test case, the elements in the array $a = [3, 23, 7]$ sum to $33$.
The xor sum of the popcounts is $2 \oplus 4 \oplus 3 = 5$. Thus, all conditions
are satisfied.
Other valid arrays are $a = [4, 2, 15, 5, 7]$ and $a = [1, 4, 0, 27, 1]$.
It can be shown that no valid arrays exist for the third test case.