codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.