[数据结构与算法]Codeforces Round #685 (Div. 2)E2. Bitwise Queries (Hard Version)题解（数学竞赛/组合构造题）

题目链接：

https://codeforces.com/contest/1451/problem/E2

大意：这是一个人机交互题。一共有N个[0, N-1]的整数，其中N是2的幂次。允许每次人指定其中两个数字与AND、OR、XOR其中一种运算，查询其计算后得到的结果。最多查询N + 1次，复现出整个数组每个数字的值。

思路：

记我们的原始的数组为A数组。

定理一：

对于非负整数x与y，有：

x + y = (x xor y) + 2 * (?x and y)

证明：按照比特位，按位计算。

1 xor 1 + (1 and 1) * 2 = 2 = 1 + 1

1 xor 0 + (1 and 0) * 2 = 1 = 1 + 0

0 xor 0 + (0?and 0) * 2 = 0 = 0 + 0

按照二进制每一位加起来，可证。

定理二：

只需要N - 1次xor查询，即可得到任何两个数字的xor结果。

证明：

已知：A[1] xor A[1] = 0 (记为v1)

记录:

A[1] xor A[2] = v2;

A[1] xor A[3] = v3;

...;

A[1] xor A[n] = vn;

那么任意两个数字A[x] xor?A[y] = A[x] xor (A[1] xor A[1]) xor A[y] = (A[x] xor A[1]) xor (A[y] xor A[1])? = vx xor vy。

那么我们可以设计方案如下：

首先先查询一遍v2, v3, ..., vn。

1、如果存在1<=i<=j<=n,vi = vj

? ? ? 那么vi xor A[1] = vj xor A[1]

? ? ? 有A[i] = A[j]，通过A[i] And A[j] = A[i]算出A[i]

? ? ? 从而可以推出其他所有的数字了。

2、如果不存在vi = vj，那么因为N是2的幂次，v的取值一定在[0, n - 1]中中间都存在。

? ? ?那么记下vx? = n - 1，二进制下全为1

? ? ?那么A[1]与A[x]一定每一位都不相同，A[1] and A[x] = 0。

? ? ?那么只需要再任意指定一个其他的数字y,查询A[1] and A[y], A[x] and A[y]的值。

? ? ?根据定理一，我们可以得到，

? ? ?A[1] + A[x] = vx

? ? ?A[x] + A[y] = 2 * (A[y] and A[x]) + (vx xor vy)

? ? ?A[1] + A[y] = 2 * (A[y] and A[1]) + vy

? ? 解三元一次方程即可。得到其中任意一个值，推出其他所有数值就行了。

代码（cf服务器崩了，还未跑出结果，下面代码暂不支持直接复制粘贴保证通过）：

#include "bits/stdc++.h"
using namespace std;
const int32_t maxN = (1 << 16) + 10;
int32_t n;
int32_t xorVal[maxN];
int32_t ans[maxN];
vector<int32_t> pos[maxN];
int32_t sendQuery(string s, int32_t i, int32_t j)
{
    cout << s << " " << i << " " << j << endl;
    cout.flush();
    int32_t ret;
    cin >> ret;
    if (ret == -1) {
        exit(0);
    };
    return ret;
}
int main()
{
    cin >> n;
    pos[0].push_back(1);
    for (int32_t i = 2; i <= n; i++) {
        int32_t ret = sendQuery("XOR", 1, i);
        xorVal[i] = ret;
        pos[ret].push_back(i);
    }
    int32_t a = 1, b, c;
    int32_t same = -1;
    for (int32_t i = 0; i < n; i++) {
        if (pos[i].size() > 1) {
            b = pos[i][0];
            c = pos[i][1];
            same = i;
        }
    }
    if (same == -1) {
        b = pos[n - 1][0];
        if (b == n) {
            c = 2;
        } else {
            c = b + 1;
        }
        int32_t xab = xorVal[b];
        int32_t xac = xorVal[c];
        int32_t xbc = xorVal[b] ^ xorVal[c];
        int32_t andac = sendQuery("AND", a, c);
        int32_t andbc = sendQuery("AND", b, c);
        int32_t ab = xab;
        int32_t ac = xac + 2 * andac;
        int32_t bc = xbc + 2 * andbc;
        ans[1] = (ab + ac - bc) / 2;
    } else {
        ans[b] = sendQuery("AND", b, c);
        ans[1] = xorVal[b] ^ ans[b];
    }
    for (int i = 2; i <= n; i++) {
        ans[i] = ans[1] ^ xorVal[i];
    }
    cout << "! ";
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    cout.flush();
    return 0;
}