Bitwise Queries (Easy Version)

发表于 分类于 ，

    有一个个未知的数组大小为n。n为2的幂次。

    数组中的值为0到n-1。

    现在最多询问n+2次，求原来的排列。

    每次询问可以询问任意两个数的：与值、或值、异或值。

Bitwise Queries (Easy Version)

Created by LXC on Sun Jun 18 00:13:47 2023

https://codeforces.com/problemset/problem/1451/E1

ranting: 2000

tag: bitmasks, constructive algorithms, interactive, math

problem

有一个个未知的数组大小为n。n为2的幂次。

数组中的值为0到n-1。

现在最多询问n+2次，求原来的排列。

每次询问可以询问任意两个数的：与值、或值、异或值。

solution

关键在于求出一个未知的值，当求一个出未知的值后，剩余的n-1个可以通过异或的性质得出。

所以有n-1次异或操作。

剩余的三次操作必须要得出一个未知数。

关键公式$a + b = a^b + 2*(a&b)$。

绞劲脑汁都没有想到的一点

当有了这个公式后，任选三个不同数，询问两两之间的与值，则可以求出两两之间的和。三个未知数三个方程，显然可以求出其中一个。

那么n+1次操作怎么做呢？

这里就需要分类讨论了，当未知排列每个数都不同时，在n-1次异或中，就必定存在一个异或和为n-1。实际上它们的与值就是0。就可以少算一步。

对于如果未知排列存在相同的数，假设我们将第2到n个数都和第1个数求异或值。
如果第2个到第n个数中存在有一个数等于第1个数，那么异或值存在0。
如果第2个到第n个数中存在相等的数，那么异或值存在相等。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

// vector<int> a = {1, 2, 0, 3};
vector<int> a = {1, 2, 0, 1};
// vector<int> a = {1, 2, 3, 3};

int getxor(int x, int y) {
    cout << "XOR " << x << " " << y << endl;
    // return a[x - 1] ^ a[y - 1];
    int rt;
    cin >> rt;
    return rt;
}
int getand(int x, int y) {
    cout << "AND " << x << " " << y << endl;
    // return a[x - 1] & a[y - 1];
    int rt;
    cin >> rt;
    return rt;
}

int xora1[(1 << 16) + 5];
int cnt[(1 << 16) + 5];

void sol() {
    int n;
    cin >> n;
    int z = -1;
    for (int i = 2; i <= n; i++) {
        xora1[i] = getxor(1, i);
        if (xora1[i] == 0)
            z = i;
        cnt[xora1[i]]++;
    }
    int p = -1;
    for (int i = 1; i < n; i++) {
        if (cnt[i] > 1) {
            p = i;
            break;
        }
    }
    vector<int> ans(n + 1);
    if (z != -1) {  // 存在0，a1 与 az 相等
        ans[1] = getand(1, z);
    } else if (p != -1) {  // a2...an中有相等
        vector<int> x;
        for (int i = 2; i <= n; i++) {
            if (xora1[i] == p)
                x.push_back(i);
        }
        int r = getand(x[0], x[1]);
        ans[1] = r ^ xora1[x[0]];
    } else {  // 不存在重复的数
        int x = 0;
        for (int i = 2; i <= n; i++) {
            if (xora1[i] == n - 1)
                x = i;
        }
        int y = (x == 2 ? 3 : 2);
        int a1x = xora1[x];
        int a1y = xora1[y] + 2 * getand(1, y);
        int ayx = (xora1[y] ^ xora1[x]) + 2 * getand(y, x);
        ans[1] = (a1x - ayx + a1y) / 2;
    }
    for (int i = 2; i <= n; i++) {
        ans[i] = ans[1] ^ xora1[i];
    }
    cout << "!";
    for (int i = 1; i <= n; i++) {
        cout << " " << ans[i];
    }
    cout << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}