백준23381 Gyrating Glyphs

작성일 | In

문제 링크

  • https://icpc.me/23381

문제 출처

  • 2021 BAPC G번

사용 알고리즘

  • 랜덤

풀이

$a_0, a_1, \cdots, a_{n-1} = 0, a_n = 1$인 쿼리의 결과를 이용해 마지막 연산자인 $op_n$을 알아낼 수 있습니다. 1이면 +, 0이면 *입니다.
비슷하게, $a_0, a_1, \cdots, a_{n-2} = 0, a_{n-1} = 1$, 그리고 $a_n$은 $op_n$의 항등원인 쿼리의 결과를 이용해 $op_{n-1}$을 알아낼 수 있습니다. 이 방법을 연속해서 사용하면 뒤에 있는 연산자부터 하나씩, 총 $n$번의 쿼리로 모든 연산자의 값을 구할 수 있습니다.

쿼리의 개수를 줄이는 것은 간단합니다. $4000 / 275 \leq 15$이므로 한 번의 쿼리를 이용해서 연산자를 15개씩 알아내면 됩니다. 가능한 $2^{15}$가지의 연산자들에 대해 서로 다른 결과를 내는 길이 15짜리 수열을 알고 있다면 쿼리마다 15개씩 알아낼 수 있습니다. 이러한 수열은 랜덤한 수열을 몇 가지 생성하다 보면 빠르게 찾을 수 있습니다.

전체 코드

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
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;

mt19937 rng(0x917917);
int Random(int l, int r){
    return uniform_int_distribution<int>(l, r)(rng);
}

bool Test(int len, const vector<int> &vec){
    set<ll> st;
    for(int bit=0; bit<(1<<len); bit++){
        ll res = 0;
        for(int i=0; i<len; i++){
            if(bit >> i & 1) res *= vec[i];
            else res += vec[i];
            res %= mod;
        }
        if(st.count(res)) return false;
        st.insert(res);
    }
    return true;
}

tuple<vector<int>, map<ll, ll>> Generate(int len){
    while(true){
        vector<int> v(len);
        for(auto &i : v) i = Random(0, mod-1);
        if(!Test(len, v)) continue;
        map<ll, ll> mp;
        for(int bit=0; bit<(1<<len); bit++){
            ll res = 0;
            for(int i=0; i<len; i++){
                if(bit >> i & 1) res *= v[i];
                else res += v[i];
                res %= mod;
            }
            assert(!mp.count(res));
            mp[res] = bit;
        }
        return {v, mp};
    }
}

string S;

int Ask(const vector<int> &v){
#ifdef LOCAL
    ll res = v[0];
    for(int i=1; i<v.size(); i++){
        if(S[i-1] == 'x') res = (res * v[i]) % mod;
        else res = (res + v[i]) % mod;
    }
    return res;
#else
    cout << "? ";
    for(auto i : v) cout << i << " ";
    cout << endl;
    int res; cin >> res;
    return res;
#endif
}

vector<int> V[16];
map<ll, ll> M[16];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

#ifdef LOCAL
    int N = 50;
    for(int i=0; i<N; i++) S += "+x"[Random(0,1)];
    cout << "! " << S << endl;
#else
    int N; cin >> N;
#endif
    for(int i=1; i<=15; i++) tie(V[i],M[i]) = Generate(i);

    vector<int> res(N+1, -1);
    if(N <= 15){
        auto vec = V[N];
        vec.insert(vec.begin(), 0);
        int now = Ask(vec);
        ll bit = M[N][now];
        cout << "! ";
        for(int i=0; i<N; i++){
            if(bit >> i & 1) cout << "x";
            else cout << "+";
        }
        cout << endl;
        return 0;
    }

    for(int i=N; i>=1; i-=15){
        int len = min(15, i);
        vector<int> now(N+1);
        for(int j=i+1; j<=N; j++) now[j] = res[j]; // 항등원
        for(int j=0; j<len; j++) now[i-len+1+j] = V[len][j];
        ll val = Ask(now); assert(M[len].count(val));
        ll bit = M[len][val];
        for(int j=0; j<len; j++) res[i-len+1+j] = bit >> j & 1;
    }
    cout << "! ";
    for(int i=1; i<=N; i++) cout << "+x"[res[i]];
    cout << endl;
}