自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:16:06，当前版本为作者最后更新于2025-05-12 22:22:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感谢 xyz123 对本题的加强建议，原版题目中只要求 $P <2^{31}$。

说句闲话：我设计这题的初衷是【模板】哈希 2，而不是【模板】通信题。

如果 A 程序可以向 B 程序传递一个不大于 $2^{31}-1$ 的非负整数，那么这就是一个 Hash 模板题。弱化后的题目随便用什么 Hash 函数都能过，比如「所有 $\texttt{1}$ 的位置编号之和 $\text{mod } 12345678$」。

然而，这道题目只允许 A 程序向 B 程序传递一个不大于 $2^{20}-1$ 的非负整数，因此我们要优化 Hash 函数——把 Hash 函数改为「所有 $\texttt{1}$ 的位置编号之异或和」就可以通过此题了。

（可以发现，对于不变动的 $N-1$ 位，设所有 $\texttt{1}$ 的位置编号之异或和为 $Q$，则第 $P$ 位为 $\texttt{0}$ 的字符串的最终 Hash 值为 $Q$，而另一个为 $Q \text{ xor } P$，二者的异或和恰好为 $P$。当 $P=0$ 时，两个 Hash 值都是 $Q$，异或和恰好也为 $P=0$。）

#include <bits/stdc++.h>
using namespace std;
int Alice(string S)
{
    int X = 0;
    int n = S.size();
    S = ' ' + S;
    for (int i = 1; i <= n; i++)
        if (S[i] == '1') X ^= i;
    return X;
}
int Bob(string T, int X)
{
    int D = 0;
    int n = T.size();
    T = ' ' + T;
    for (int i = 1; i <= n; i++)
        if (T[i] == '1') X ^= i;
    return X;
}