「Cfz Round 2」Binary

Luogu

IDLGP10307

Time1000ms

Memory512MB

DifficultyP3

模拟洛谷原创O2优化位运算洛谷月赛

给定 $n + 1$ 个整数 $a_0\dots a_n$。对于整数 $u$，设它在二进制下为 $1$ 的位分别为 $k_1, k_2\dots k_m$，那么它的权值 $f(u) = a_{k_1} \oplus a_{k_2} \oplus \dots \oplus a_{k_m}$。此处的二进制位的编号从右到左，依次为 $0,1,2\dots$。其中 $\oplus$ 表示 [按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fromModule=search-result_lemma-recommend) 符号。你想要知道有多少个 $0 \leq u \leq 2^n - 1$ 使得 $f(u) = f(u + 1)$。为了方便，请你用 **二进制形式** 输出答案（不取模）。请注意：输出不能包含前导 $0$，除非答案为 $0$。 ## Input **本题有多组测试数据。** 第一行输入一个整数 $T$，表示测试数据组数。接下来依次输入每组测试数据。对于每组测试数据： - 第一行输入一个正整数 $n$。 - 第二行输入 $n + 1$ 个整数 $a_0 \dots a_n$。 ## Output 对于每组数据，输出一行一个二进制整数，表示答案。再次提示：输出不能包含前导 $0$，除非答案为 $0$。 [samples] ## Note #### 「样例解释 #1」对于第 $1$ 组数据， - $(0)_{10} = (0)_{2}$，所以 $f(0) = 0$； - $(1)_{10} = (1)_{2}$，所以 $f(1) = a_0 = 0$； - $(2)_{10} = (10)_{2}$，所以 $f(2) = a_1 = 1$； - $(3)_{10} = (11)_{2}$，所以 $f(3) = a_0 \oplus a_1 = 0 \oplus 1 = 1$； - $(4)_{10} = (100)_{2}$，所以 $f(4) = a_2 = 2$。这其中有 $f(0) = f(1)$，$f(2) = f(3)$，所以输出 $(2)_{10} = (10)_{2}$。 #### 「数据范围」设 $\sum n$ 表示单个测试点中 $n$ 的和。对于所有数据，$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$。 **只有你通过本题的所有测试点，你才能获得本题的分数。**

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「Cfz Round 2」Binary",
    "description": {
      "content": "给定 $n + 1$ 个整数 $a_0\\dots a_n$。 对于整数 $u$，设它在二进制下为 $1$ 的位分别为 $k_1, k_2\\dots k_m$，那么它的权值 $f(u) = a_{k_1} \\oplus a_{k_2} \\oplus \\dots \\oplus a_{k_m}$。此处的二进制位的编号从右到左，依次为 $0,1,2\\dots$。其中 $\\oplus$ 表示 [按位异或]",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10307"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n + 1$ 个整数 $a_0\\dots a_n$。\n\n对于整数 $u$，设它在二进制下为 $1$ 的位分别为 $k_1, k_2\\dots k_m$，那么它的权值 $f(u) = a_{k_1} \\oplus a_{k_2} \\oplus \\dots \\oplus a_{k_m}$。此处的二进制位的编号从右到左，依次为 $0,1,2\\dots$。其中 $\\oplus$ 表示 [按位异或]...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments