题解：AT_agc031_c [AGC031C] Differ by 1 Bit

zesqwq · 2024-09-07 19:07:15 · 题解

[AGC031C] Differ by 1 Bit sol

下文中用 \oplus 表示异或。

一个很简单的套路题，就是在已知能简单判断是否合法的情况下递归构造。

首先我们发现，如果 \text{popcnt}(A\oplus B) 是偶数显然无解，否则我断言它就是有解的。

那假设这个断言是正确的，考虑递归构造，我们发现这个构造看着就很松，我们可以大胆想象：我们取出 A\oplus B 的最高位 g，然后考虑构造 A,...,A\oplus t 和 A\oplus t\oplus 2^g,...,B 这样的序列。

那么我们发现，如果 t 二进制下不包含 2^g 且 \text{popcnt}(t) 是奇数，那么我们就可以递归构造，也就是说我们定义 \text{solve}(A, B, \{S\}) 表示要构造由 A 到 B 的并且只有 S 中的这些二进制位可以作为相邻两个的异或值。

那么显然可以递归到 \text{solve}(A, B, \{S\}) = \text{solve}(A, A\oplus t, \{S\}- 2^g) + \text{solve}(A\oplus t \oplus 2^g, B, \{S\}- 2^g)。

那么我们就找到这样的 t 后递归构造就好了，发现总是能找到的，于是就做完了。

const int N = 1 << 20;

inline basic_string<int> solve(int n, int A, int B, int fw) {
    if (n == 1) return {A, B};
    int kel = A ^ B;
    int c = __lg(kel);
    for (int t = fw;; t = (t - 1) & fw) {
        if ((t >> c & 1 ^ 1) && __builtin_parity(t)) {
            auto a = solve(n - 1, A, A ^ t, fw ^ (1 << c));
            auto b = solve(n - 1, A ^ t ^ (1 << c), B, fw ^ (1 << c));
            return a + b;
        }
        if (t == 0) break;
    }
    assert(0);
}
int n, x, y;
int main() {
    read(n, x, y);
    if (!__builtin_parity(x ^ y)) return println("NO"s), 0;
    println("YES"s);
    auto c = solve(n, x, y, (1 << n) - 1);
    for (int v : c) write(v, ' ');
    return 0;
}