题解：AT_agc045_a [AGC045A] Xor Battle

由于是线性基专题，于是直接对整个序列套线性基想了半天，发现不可做。

于是还是要从简单的情况想起。

考虑已经进行完了

n-1

次操作，当前的数是

x

，

若 $s_n=1$ ， $1$ 必胜。
若 $s_n=0$ ，当且仅当 $x=0$ 或 $x=a_n$ ， $0$ 必胜。

我们发现维护

0

的必胜集合似乎比

1

容易一些。

设

F_i

表示进行完

i-1

轮后，能使

0

必胜的

x

的取值集合，

F_n=\begin{cases}\{0,a_n\} & s_n=0 \\ \varnothing & s_n=1\end{cases}

，

F_i=\begin{cases}\{x\mid x\in F_{i+1} \vee x\oplus a_i \in F_{i+1}\} & s_n=0 \\ \{x\mid x\in F_{i+1} \wedge x\oplus a_i \in F_{i+1}\} & s_n=1\end{cases}

，

直接用 set 维护会 TLE，考虑优化。

考虑一个

F_i

，如果

s_i \cdots s_n

全部都是

0

，那么

F_i

其实就是

a_i \cdots a_n

的异或生成空间。

考虑倒数第一个

s_i=1

的位置，若

a_i\in F_{i+1}

，则整个

F_{i+1}

都是满足条件的，可以直接继承过来；若

a_i\notin F_{i+1}

，那么不存在

x\in F_{i+1}

，使得

x\oplus a_i\in F_{i+1}

，于是这时候

F_i=\varnothing

，直接判

1

必胜即可。

这样我们就处理了

s_i=1

的情况，

倒着扫一遍，用线性基维护即可。

CPP

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UI = unsigned int;
using ULL = unsigned long long;
using DB = double;
using LDB = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define CP(x) complex<x>
#define fst first
#define snd second
#define popcnt(i) __builtin_popcount(i)

const int N = 2e2 + 5;

int n;
string s;
LL a[N];

struct Basis {
    int n;
    LL b[65];

    void init(int _n) {
        n = _n;
        for (int i = 0; i <= n; i++) {
            b[i] = 0;
        }
    }

    void insert(LL x) {
        for (int i = n; i >= 0; i--) {
            if ((x >> i) & 1) {
                if (!b[i]) {
                    b[i] = x;
                    return;
                }
                x ^= b[i];
            }
        }
    }

    bool find(LL x) {
        for (int i = n; i >= 0; i--) {
            if ((x >> i) & 1) {
                if (!b[i]) {
                    return false;
                }
                x ^= b[i];
            }
        }
        return true;
    }
} B;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> s;
    s = ' ' + s;
    B.init(60);
    for (int i = n; i >= 1; i--) {
        if (s[i] == '0') {
            B.insert(a[i]);
        } else if (!B.find(a[i])) {
            cout << 1 << '\n';
            return;
        }
    }
    cout << 0 << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

题解：AT_agc045_a [AGC045A] Xor Battle

文章操作

相关推荐

评论

题解：AT_agc045_a [AGC045A] Xor Battle