本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-04 16:09:08

题意还是比较明确的。首先我们需要知道异或的两个性质：$a\oplus a = 0$ 与 $a\oplus 0 = a$。

遇到没思路的时候，先来看几个栗子：

• $(1000)_2 + 1 = (0001)_2$，$k$ 从 $(3)$ 变成 $(0, 3)$，那么 $f(u + 1) = f(u) \oplus a_0$。

• $(0011)_2 + 1 = (0100)_2$，$k$ 从 $(0, 1)$ 变成 $2$，$f(u + 1) = f(u) \oplus a_0 \oplus a_1 \oplus a_2$。

• $(1111)_2 + 1 = (10000)_2$，$k$ 从 $(0, 1, 2, 3)$ 变成 $(4)$，$f(u + 1) = f(u) \oplus a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4$。

观察到：如果 $u + 1$ 进了 $k$ 位，就有 $f(u + 1) = f(u)\oplus \sigma_k$，其中 $\sigma_k = \bigoplus\limits_{i=0}^k a_i$，即 $a$ 的前缀异或和。由题意，$f(u + 1) = f(u)$，故 $\sigma_k = 0$。然后考虑怎么统计答案。

如果 $u + 1$ 进了 $k$ 位，就意味着它的低 $k$ 位全都是 $1$，那么就剩下 $n - k - 1$ 位可以选，也就是 $2^{n - k - 1}$ 种方案。

换句话说，每一个 $\sigma_k = 0$ 的 $k$，都会产生 $2^{n - k - 1}$ 的贡献。 题意中让我们输出二进制表示，于是我们将答案的第 $n - k - 1$ 位置一即可。

最后考虑一个边缘情况：$\sigma_n = 0$，即样例二。这种情况特判，将最终答案加一即可。

赛时码：

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int res[N];

int main (void)
{
    int t;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> t;
    while (t--) {
        int n, sum = 0, high = 0;

        cin >> n;
        for (int i = 0; i <= n; i++) {
            int v;
            cin >> v;
            if ((sum ^= v) == 0 && i < n) res[n - i - 1] = 1, high = max (high, n - i - 1);
        }

        if (!sum) {
            int q = 0;
            while (res[q]) res[q++] = 0;
            res[q] = 1;
        }
        for (int i = high; i >= 0; i--) cout << res[i];
        cout << '\n';
        for (int i = 0; i <= high; i++) res[i] = 0;
    }
    return 0;
}