题意回顾

• 有 $n$ 轮，第 $i$ 轮时，如果 $c_i = 0$，水母（最小化者）操作；如果 $c_i = 1$，花花（最大化者）操作。
• 操作：$x \leftarrow x \oplus a_i$ 或 $x \leftarrow x \oplus b_i$。
• 初始 $x = 0$，问最优情况下最后的 $x$。

---

核心思路

第一步：变量转化

设初始 $x = 0$，但更方便的是设初始 $x = \bigoplus_{j=1}^{n} a_j$，这样选择 $a_i$ 相当于 $x$ 不变，选择 $b_i$ 相当于 $x$ 再异或上 $a_i \oplus b_i$。

令

$$d_i = a_i \oplus b_i$$

那么在第 $i$ 轮：

• 选择 $a_i$：$x$ 不变
• 选择 $b_i$：$x \leftarrow x \oplus d_i$

所以游戏变成：

• 初始 $x = \bigoplus_{i=1}^n a_i$
• 对 $i = 1 \dots n$，如果 $c_i = 0$（水母），她可以选择 $x$ 不变或 $x \leftarrow x \oplus d_i$，并希望最终 $x$ 最小；
  如果 $c_i = 1$（花花），她选择 $x$ 不变或 $x \leftarrow x \oplus d_i$，希望最终 $x$ 最大。

这是一个带选择权的线性基博弈。

---

第二步：逆序处理

从后往前考虑。
设 $f(x)$ 表示从当前轮开始到结束，在双方最优策略下最终的 $x$ 值（当前 $x$ 是某个初始值）。
我们发现 $f$ 是仿射变换：

$$f(x) = A x \oplus b$$

其中 $A$ 是一个线性（异或）变换（可逆? 不一定全空间），$b$ 是一个常数向量（异或意义上）。

当 $n=0$ 时，$f(x) = x$，即 $A = I, b = 0$。

---

第三步：一次逆序递推

假设我们从后面前已经处理好了后面的 $n-1$ 轮，得到了当前 $f(x) = A x \oplus b$。
现在考虑前面的一轮，给定 $d_i$ 和 $c_i$（最小化/最大化）。

该轮操作后：

• 如果不异或 $d_i$，结果 = $f(x)$
• 如果异或 $d_i$，结果 = $f(x \oplus d_i)$

因为：

$$f(x \oplus d_i) = A (x \oplus d_i) \oplus b = (A x \oplus b) \oplus (A d_i) = f(x) \oplus (A d_i) $$

所以两选项的差异是常数 $t = A d_i$。

---

关键：设 $t = A d_i$。
如果 $c_i = 0$（水母，最小化者），她会在 $f(x)$ 和 $f(x) \oplus t$ 中选择更小的。
如果 $c_i = 1$（花花，最大化者），她会选更大的。

这决定依赖于 $f(x)$ 的最高不同位（即 $t$ 的最高位 $k$）在 $f(x)$ 中是 0 还是 1。

---

第四步：线性基维护

我们要维护 $A$ 和 $b$ 的信息。
实际上，$A$ 是一个线性变换，我们可以用线性基来表示它的零空间和像空间。

标程的做法是：

• 用一个线性基 bas 来存储所有 $d_i$ 经过 $A$ 映射后的值（即 $A d_i$）的一些信息。
• 给基向量打标记 bel[i]，表示这个基向量对应的 $t$ 在插入时，是由最小化者还是最大化者控制的。

具体：

• 初始化 $A = I$（空基）。
• 从 $i=n$ 到 $1$ 逆序处理：
  • 令 $x = d_i$
  • 把 $x$ 插入到线性基中（用标准的线性基插入，但要保证基是上三角形式）
  • 在插入时，如果 $x$ 变成非零基向量，那么它的最高位 $k$ 对应 $t$ 的最高位，决定它是“增加”还是“减少”。

这里的 bel[k] 标记这个基向量是由谁控制的（$0$ 或 $1$）。

---

第五步：最终计算

在逆序过程中，我们实际上在做：

• 从后往前，每个 $d_i$ 可能会引入新的基向量（如果不被已有基表示），这个基向量可以理解为 $A d_i$ 在像空间的一个坐标轴。
• 所有 $b_i$ 的控制者决定了这个轴在最终 $x$ 中是保留还是取消（因为最优策略会选）。

最终：

• 初始 $all = \bigoplus a_i$
• 然后把 $all$ 在基中尽量消去（即从高到低，如果 $all$ 某位有 1，则异或对应的基向量），表示最终 $x$ 的“不可控部分”。
• 再把所有 $bel[k] = 1$（花花控制）的基向量异或回 $ans$，表示这些是花花可以强制变成 1 的位。

最终答案 = $all \oplus ans$。

---

代码实现

int n; 
std::cin >> n;
std::vector<i64> a(n), b(n);
std::string str;
i64 all = 0;
for(auto &x : a) std::cin >> x, all ^= x;  // 初始 all = XOR a_i
for(int i = 0; i < n; i ++) {
    std::cin >> b[i];
    b[i] ^= a[i];   // 变成 d_i = a_i ^ b_i
}
std::cin >> str;    // c 字符串

std::vector<i64> bas(L);   // 线性基
std::vector<int> bel(L, -1); // 基向量的控制者标记

for(int i = n - 1; i >= 0; i --) {  // 逆序处理
    i64 x = b[i];   // x = d_i
    int col = str[i] - '0'; // 0 或 1
    // 标准线性基插入，但要保持上三角形式
    for(int i = L - 1; i >= 0; i --) if(x >> i & 1) {
        if(bas[i]) {
            x ^= bas[i];
        } else {
            // 消去低位
            for(int j = i - 1; j >= 0; j --) if(x >> j & 1) {
                x ^= bas[j];
            }
            bas[i] = x;
            // 消去高位
            for(int j = L - 1; j > i; j --) if(bas[j] >> i & 1){
                bas[j] ^= bas[i];
            }
            bel[i] = col;   // 记录这个基向量的控制者
            break;
        }
    }
}

// all 在基中消去
for(int i = L - 1; i >= 0; i --) if(all >> i & 1) {
    all ^= bas[i];
}

// 收集花花（控制者 1）可以控制的基向量
i64 ans = 0;
for(int i = 0; i < L; i ++) if(bel[i] == 1) ans ^= bas[i];

std::cout << (all ^ ans) << '\n';

---

复杂度

• 每个 $d_i$ 插入线性基 $O(\log \max)$
• $n$ 总和 $\le 10^5$，每位 $60$ 位
• 总复杂度 $O(n \log \max)$

---

总结

该解法核心：

1. 把 $a_i, b_i$ 转化为 $d_i = a_i \oplus b_i$ 和初始 $x_0 = \bigoplus a_i$。
2. 逆序处理，用线性基维护 $A d_i$ 的信息。
3. 通过基向量控制者标记，决定哪些位最终能被花花固定为 1。
4. 最后得到答案。