「解题报告」[ARC145E] Adjacent XOR

· · 题解

2022 做的最后一道题——

还是很有意思的一个构造题。

upd. 2023.1.26 修了一个问题 感谢 @歌吟入梦 orz

思路

题目中要求让 a_i \gets a_i \oplus a_{i-1}，可以把它看作一个差分。我们用它的逆运算，也就是前缀异或和来考虑这个问题。那么我们就把问题转换成了：给定 b 数组，每次可以选取 k \in [1, n]，然后将 i \in [1, k] 中的所有 b_i \gets \bigoplus_{j=1}^i b_j，求一个将 b 数组转换成 a 数组的方案。

观察数据范围，发现大约是 n \log b，那么我们可以考虑每次用 \log b 次操作凑出一个 a_i。为了防止前缀和影响之前凑好的数，我们考虑从 a_n 到 a_1 凑。

首先我们可以得到一个 Yes 的必要条件：每一个 a_i 都可以由 \{ b_1, \cdots, b_{i-1}\} 中的若干数与 b_i 异或得到。

事实上，这也是一个充分条件，下面我们来尝试构造。

首先原数组看起来就很不好考虑，我们可以对它们求一个线性基，然后给基底按照加入的先后顺序标一个号，再用这组基底新的标号来表示 b 中的每一个数。不难发现，进行这一步转换后，对得到的新数组 c 进行操作和对原数组 b 进行操作时等价的。那么我们就来考虑这个新的 c 数组。

此时我们要构造的目的还不明确。但是注意到我们是从 a_n 到 a_1 进行构造，如果此时我们要构造 a_i，那么我们是不能对 k \in (i, n] 进行操作的，否则会将之前已经构造好的数打乱掉。也就是说，想要改变 b_i 只有可能对 k=i 进行操作。对 k=i 进行操作相当于将 b_i \gets \bigoplus_{j=1}^i b_j。那么，我们实际上就是要构造出异或和等于 a_i。

可以发现，由于我们按照加入的先后顺序进行标号，那么如果第 i 位最早在 pos_i 出现了，那么在 1 \sim pos_i - 1 中 i 这一位都为 0。

考虑如何将前缀和的某一位翻转。我们知道 pos_i 是第一次出现 i，那么如果对 k=pos_i + 1 进行操作，只有 b_{pos_i + 1} 的异或和多了 i 这一位，那么总异或和的这一位也就会被翻转。我们从大到小考虑，这样 pos_i 是递减的，操作不会影响到之前的数。

那么我们就有了一个构造方法：从大到小枚举每一位 i，计算出当前的异或和，如果在 i 这一位上 a_i（在重标号后的）与异或和这一位不一样，就对 k=pos_i+1 进行操作，最后再对 k=m 进行一次操作，就能构造出 a_m 了。

将这个过程重复 n 遍即可。最后再把操作序列翻转过来，就是 a 到 b 的操作了。

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
long long a[MAXN], b[MAXN], c[MAXN];
int pos[64];
vector<int> ans;
struct LinearBasis {
    long long a[63];
    int id[63];
    int tot;
    bool contains(long long x) {
        for (int i = 59; i >= 0; i--) if (x >> i & 1) {
            if (a[i]) {
                x ^= a[i];
            } else {
                return false;
            }
        }
        return true;
    }
    long long insert(long long x) {
        long long ret = 0;
        for (int i = 60; i >= 0; i--) if (x >> i & 1) {
            if (a[i]) {
                ret |= (1ll << id[i]);
                x ^= a[i];
            } else {
                a[i] = x;
                id[i] = tot++;
                return ret | 1ll << (id[i]);
            }
        }
        return ret;
    }
    void clear() {
        memset(a, 0, sizeof a);
        memset(id, 0, sizeof id);
        tot = 0;
    }
} lb;
void filp(int x) {
    ans.push_back(x);
    for (int i = 1; i <= x; i++) {
        b[i] ^= b[i - 1];
        c[i] ^= c[i - 1];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!lb.contains(a[i] ^ b[i])) { // 判断是否有解
            printf("No\n");
            return 0;
        }
        lb.insert(b[i]);
    }
    for (int i = n; i >= 1; i--) {
        lb.clear();
        for (int j = 1; j <= i; j++) {
            bool isIn = lb.contains(b[j]); // 是否在线性基里，如果不在那就是有新的基底，记录第一次出现位置 pos_i
            c[j] = lb.insert(b[j]);
            if (!isIn) {
                pos[__lg(c[j])] = j;
            }
        }
        long long goal = lb.insert(a[i]);
        for (int j = lb.tot - 1; j >= 0; j--) {
            long long sum = 0;
            for (int k = 1; k <= i; k++) sum ^= c[k];
            if ((sum >> j & 1) != (goal >> j & 1)) filp(pos[j] + 1);
        }
        filp(i);
    }
    reverse(begin(ans), end(ans));
    printf("Yes\n%lu\n", ans.size());
    for (int i : ans) printf("%d ", i);
    printf("\n");
    return 0;
}