2239A.md (2927B)
1 Source: https://codeforces.com/problemset/problem/2239/A 2 3 A. Nim Game Is XOR Game 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 Alice and Bob are playing a game with an array $a$ consisting of $n$ non-negative integers. Alice goes first. 22 23 In each turn, the current player must choose an array of $n$ non-negative integers $b = [b_1, b_2, \ldots, b_n]$ that satisfies the following conditions: 24 25 1. $0 \le b_i \le a_i$ for all $1 \le i \le n$; 26 2. $\sum_{i=1}^n b_i \gt 0$ (i.e. the array $b$ does not consist entirely of zeros); 27 3. $b_1 \oplus b_2 \oplus \ldots \oplus b_n = 0$, where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 28 29 After choosing the array $b$, the player updates the array $a$ by performing $a_i \leftarrow a_i - b_i$ for all $1 \le i \le n$. 30 31 The player who cannot perform such an operation loses the game. 32 33 Determine the number of valid choices for the array $b$ that Alice can make on her first turn to guarantee a win, assuming both players play optimally. Since this number may be large, output the answer modulo $998\,244\,353$. 34 35 Input 36 37 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. 38 39 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the array $a$. 40 41 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \lt 2^{30}$) — the contents of the array $a$ 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$. 44 45 Output 46 47 For each test case, output the number of valid choices for the array $b$ that Alice can make on her first turn to guarantee a win modulo $998\,244\,353$. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 1 57 58 1 59 60 2 61 62 1 2 63 64 5 65 66 1 4 5 2 6 67 68 1 69 70 1073741823 71 72 3 73 74 1 2 3 75 ``` 76 77 Output 78 79 ``` 80 0 81 82 1 83 84 3 85 86 0 87 88 1 89 ``` 90 91 Note 92 93 In the first test case, Alice must choose an array $b$ of length $1$. The conditions require $b_1 \le a_1$, $b_1 \gt 0$, and $b_1 = 0$. It is impossible to satisfy $b_1 \gt 0$ and $b_1 = 0$ simultaneously. Thus, Alice has no valid moves and loses immediately. The answer is $0$. 94 95 In the second test case, $a = [1, 2]$. Alice must choose $b = [b_1, b_2]$. The condition $b_1 \oplus b_2 = 0$ implies that $b_1 = b_2$. Since $0 \le b_1 \le 1$ and $0 \le b_2 \le 2$, and the array $b$ cannot consist entirely of zeros, the only valid choice is $b = [1, 1]$. If Alice chooses $b = [1, 1]$, the array updates to $a = [1-1, 2-1] = [0, 1]$. Now it is Bob's turn. Similar to Alice's situation, Bob must choose $b'$ such that $b'_1 = b'_2$. Since $a_1 = 0$, he is forced to pick $b'_1 = 0$, which means $b'_2 = 0$. Since a valid move must have $\sum b'_i \gt 0$, Bob has no valid moves and loses. Therefore, $b = [1, 1]$ is a winning move for Alice, and the answer is $1$.