「AtCoder ABC126-F」XOR Matching

Description

构造一个序列 $\{a\}$，这个序列的长度是 $2^{m + 1}$，且 $0 \sim 2^m - 1$ 中的每一个整数都必须出现 $2$ 次。对于任何 $a_i = a_j\ (i < j)$，都满足 $a_i \oplus a_{i + 1} \oplus \cdots \oplus a_{j - 1} \oplus a_j = k$ 。如果不存在这样的序列输出 -1 。$(0 \leq m \leq 17,0 \leq k \leq 10^9)$

Source

[AtCoder]ABC126-F

Solution

显然当 $k > 2^m - 1$ 时无解，因为 $2^m - 1$ 的每一个二进制位都是 $1$，与比它小的数异或后不可能大于 $2^m - 1$ 。

考虑构造一个合法的序列。

我们在中间放一个数 $k$，然后在其两边放相同的数，比如：

$0,1,2,3,\ldots ,2^m - 1,k,2^m - 1,\ldots,3,2,1,0$

这显然是没有问题的，因为对于任意两个相同的数，它们中间两两相同的数能互相抵消为 $0$，最终的异或和一定是 $k$ 。如果按这种方法构造，可以让除了 $k$ 之外的所有数符合条件，但是还多了一个 $k$，考虑这个 $k$ 应该放在哪里。

我们可以通过异或运算的性质得到一个结论：

$n$ 为大于 $1$ 的整数时，存在

$0 \oplus 1 \oplus 2 \oplus \cdots \oplus (2^n - 1) = 0$

证明：

将它们两两异或得到一个新的序列。

$\begin{aligned} 0 \oplus (2^n - 1) &= 2^n - 1\\[1ex] 1 \oplus (2^n - 2) &= 2^n - 1\\[1ex] 2 \oplus (2^n - 3) &= 2^n - 1\\[1ex] \cdots &\cdots\\[1ex] (2^{n - 1} -1) \oplus 2^{n - 1} &= 2^n - 1 \end{aligned}$

显然异或后只剩下 $2^{n - 1}$ 个 $2^n - 1$，根据异或运算的性质（偶数个相同数的异或和为 $0$）得到：当 $n > 1$ 时，$2^{n - 1}$ 一定为偶数，该式子的值为 $0$ 得证。

因此我们只需要将另一个 $k$ 放在最后即可，这样两个 $k$ 中间的数与其中一个 $k$ 的异或和刚好为 $0$，$0$ 异或另一个 $k$ 的值为 $k$ 。最后注意 $n = 1$ 时结论不成立需要特判。时间复杂度为 $O(n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = (1 << 18) + 5;
int n, m, k, maxn, ans[MAXN + 5];

int main() {
    read(m), read(k);
    maxn = (1 << m) - 1, n = 1 << (m + 1);
    if (m == 1) {//特判 m = 1 
        if (k == 0) puts("0 0 1 1");
        else puts("-1");
        return 0;
    }
    if (k > maxn) {//无解 
        puts("-1");
        return 0;
    }
    ans[n / 2] = ans[n] = k;//中间和末项都是 k 
    for (int p = 0, i = 1; i <= maxn; ++i, ++p) {
        if (p == k) ++p;//k 已经被占用，k 的两边不能放 k 
        ans[i] = ans[n - i] = p;//对称地在 k 两边放数 
    }
    for (int i = 1; i <= n; ++i) {
        write(ans[i]);
        putchar(' ');
    }
    putchar('\n');
    return 0;
}