题解：AT_agc045_a [AGC045A] Xor Battle
chenwenmo
·
·
题解
由于是线性基专题，于是直接对整个序列套线性基想了半天，发现不可做。
于是还是要从简单的情况想起。
考虑已经进行完了 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_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;
}
```