#1494. 「Cfz Round 2」Binary

「Cfz Round 2」Binary

题目描述

给定 n+1n + 1 个整数 a0…ana_0\dots a_n。

对于整数 uu,设它在二进制下为 11 的位分别为 k1,k2…kmk_1, k_2\dots k_m,那么它的权值 $f(u) = a_{k_1} \oplus a_{k_2} \oplus \dots \oplus a_{k_m}$。此处的二进制位的编号从右到左,依次为 0,1,2…0,1,2\dots。其中 ⊕\oplus 表示 按位异或 符号。

你想要知道有多少个 0≤u≤2n−10 \leq u \leq 2^n - 1 使得 f(u)=f(u+1)f(u) = f(u + 1)。为了方便,请你用 二进制形式 输出答案(不取模)。

请注意:输出不能包含前导 00,除非答案为 00。

输入格式

本题有多组测试数据。

第一行输入一个整数 TT,表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行输入一个正整数 nn。
  • 第二行输入 n+1n + 1 个整数 a0…ana_0 \dots a_n。

输出格式

对于每组数据,输出一行一个二进制整数,表示答案。

再次提示:输出不能包含前导 00,除非答案为 00。

样例

5
2
0 1 2
3
1 3 3 1
4
2 2 5 4 2
5
7 0 3 4 0 1
6
5 2 1 8 6 0 9
10
1
100
11
0

题目来源:洛谷 P10307