2160C.md (1537B)
1 Source: https://codeforces.com/problemset/problem/2160/C 2 3 C. Reverse XOR 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given a positive integer $x$, let $f(x)$ be the positive integer formed by reversing the binary representation of $x$ without leading zeroes. For example, if $x=12=1100_2$, then $f(x)=0011_2=3$. 22 23 You are given an integer $n$. Please determine if there exists a positive integer $x$ such that $x \oplus f(x) = n$$^{\text{∗}}$. 24 25 $^{\text{∗}}$Here, $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 The first line of each test case contains an integer $n$ ($0 \leq n \lt 2^{30}$). 32 33 Output 34 35 For each test case, output YES if there exists a positive integer $x$ such that $x \oplus f(x) = n$, and NO otherwise. 36 37 You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" are also recognized as positive responses. 38 39 Example 40 41 Input 42 43 ``` 44 6 45 46 0 47 48 3 49 50 6 51 52 8 53 54 10 55 56 11 57 ``` 58 59 Output 60 61 ``` 62 YES 63 64 YES 65 66 YES 67 68 NO 69 70 YES 71 72 NO 73 ``` 74 75 Note 76 77 In the first case, when $x=1$, $f(x)=1$, and $x \oplus f(x)=0$. Thus, the answer is YES. 78 79 In the second case, when $x=2$, $f(x)=1$, and $x \oplus f(x)=3$. Thus, the answer is YES. 80 81 In the fourth test case, we can show there is no $x$ that satisfies $x \oplus f(x)=8$, so the answer is NO.