题意简述

给定 $n$ 个 $k$ 位二进制数 $a_i$ 和目标二进制数 $s$（均为 $k$ 位）。求一个 $k$ 位非负整数 $x$，使得 $\sum_{i=1}^n (a_i \oplus x) = s$。若不存在输出 $-1$。

位运算性质

按位异或对加法没有简单的线性关系，但我们可以逐位考虑贡献，并结合进位进行 DP。

设 $x$ 的二进制表示为 $x_{k-1} \dots x_0$（下标从低位到高位，输出要求从高位到低位，处理时可反转）。对于每一位 $j$，$a_i \oplus x$ 的第 $j$ 位等于 $a_{i}^{(j)} \oplus x_j$。该位的总和加上来自低位的进位，最终必须匹配 $s$ 的第 $j$ 位。

令 cnt[j] 表示第 $j$ 位上 $n$ 个数中 1 的个数。若 $x_j = 0$，则该位对总和的贡献为 cnt[j]；若 $x_j = 1$，则贡献为 $n - cnt[j]$（因为 1 翻转成 0，0 翻转成 1）。

DP 设计

从低位向高位处理，设 cur 为处理完当前位后向高位的进位。状态 $(i, cur)$ 表示已决策了低 $i$ 位，当前进位为 cur。转移时，枚举 $x_i \in \{0, 1\}$：

• 该位总和 sum_bit = (x_i == 0 ? cnt[i] : n - cnt[i]) + cur
• 要求 sum_bit % 2 == s_i（$s_i$ 是 $s$ 的低 $i$ 位）。
• 若满足，则新进位 new_cur = sum_bit / 2，递归到下一位。

由于进位 cur 最大不会超过 $n$（因为每一位的贡献最多 $n$，进位连续累加也不会超过 $n$），所以 DP 状态数为 $O(k \cdot n)$。直接记忆化搜索即可。若所有位处理完且进位为 $0$，则成功找到 $x$。

实现细节

• 输入时字符串是高位到低位，需反转处理（低位对齐数组下标 0）。
• 用 cnt 数组统计每一位上 $a_i$ 的 1 的个数。
• 使用 memo[i][cur] 记录已访问状态，避免重复搜索。
• 搜索过程中记录选择的 $x$ 的每一位（低位），最后反转得到高位到低位的输出。

复杂度

总状态数 $O(nk)$，每次转移 $O(1)$。总复杂度与输入规模 $O(\sum nk)$ 同阶，可轻松通过 $2\times 10^6$ 的限制。

参考代码

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<vector<bool>> memo;
string res;
vector<int> cnt;
string s;

bool rec(int i, int cur) {
    if (i == k) {
        if (cur == 0) {
            return true;
        }
        return false;
    }
    if (memo[i][cur]) return false;
    memo[i][cur] = true;
    for (int c = 0; c < 2; ++c) {
        int q = cur;
        if (c == 0) q += cnt[i];
        else q += n - cnt[i];
        if ((q & 1) == s[i] - '0') {
            if (rec(i + 1, q / 2)) {
                res += char(c + '0');
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        cin >> n >> k;
        cin >> s;
        reverse(s.begin(), s.end());
        cnt = vector<int>(k);
        for (int i = 0; i < n; ++i) {
            string t;
            cin >> t;
            reverse(t.begin(), t.end());
            for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0';
        }
        memo = vector<vector<bool>>(k, vector<bool>(n, false));
        res = "";
        rec(0, 0);
        if (res.empty()) cout << "-1\n";
        else cout << res << '\n';
    }
}