P10307 "Cfz Round 2" Binary

You are given $n + 1$ integers $a_0 \dots a_n$. For an integer $u$, suppose the bit positions where its binary representation is $1$ are $k_1, k_2 \dots k_m$. Then its weight is $f(u) = a_{k_1} \oplus a_{k_2} \oplus \dots \oplus a_{k_m}$. Here, the binary bit positions are numbered from right to left as $0,1,2\dots$. The symbol $\oplus$ denotes the [bitwise XOR](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fromModule=search-result_lemma-recommend). You want to know how many integers $0 \leq u \leq 2^n - 1$ satisfy $f(u) = f(u + 1)$. For convenience, please output the answer in **binary form** (no modulo). Note: The output must not contain leading $0$, unless the answer is $0$.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. Then the test cases follow. For each test case: - The first line contains a positive integer $n$. - The second line contains $n + 1$ integers $a_0 \dots a_n$.

For each test case, output one line containing a binary integer, which is the answer. Reminder: The output must not contain leading $0$, unless the answer is $0$.

#### "Sample Explanation #1" For the first test case: - $(0)_{10} = (0)_{2}$, so $f(0) = 0$. - $(1)_{10} = (1)_{2}$, so $f(1) = a_0 = 0$. - $(2)_{10} = (10)_{2}$, so $f(2) = a_1 = 1$. - $(3)_{10} = (11)_{2}$, so $f(3) = a_0 \oplus a_1 = 0 \oplus 1 = 1$. - $(4)_{10} = (100)_{2}$, so $f(4) = a_2 = 2$. Among them, we have $f(0) = f(1)$ and $f(2) = f(3)$, so the output is $(2)_{10} = (10)_{2}$. #### "Constraints" Let $\sum n$ be the sum of $n$ within a single test file. For all testdata, $1 \leq T \leq 10^3$, $1 \leq n \leq 2\times 10^5$, $\sum n \leq 6\times 10^5$, $0 \leq a_i \leq 2^{30} - 1$. **Only if you pass all test points of this problem can you get the score for this problem.** Translated by ChatGPT 5