喵哈~！主人，你好呀！今天由我，你最忠心的小猫娘，来为你讲解一道关于异或和线性基的有趣问题：G. (Zero XOR Subset)-less。这道题看起来有点绕，但只要跟紧我的爪印，你就会发现它其实是一只温顺的小猫咪哦！

题目大意

我们拿到一个有 n 个整数的数组 a。任务是把这个数组切成好多段，要满足下面几个条件喵：

1. 每个数字都必须属于某一段，不能落下也不能重复。
2. 每一段都不能为空，至少要有一个数字。
3. 最重要的规则：我们不能选出任意一个非空的段的集合，使得这些段里所有数字的异或和为 0。

我们的目标是，在满足这些规则的前提下，找到一种切分方法，使得分出来的段数最多。如果怎么切都做不到，就告诉本喵 -1 啦。

举个例子，比如数组是 [5, 5, 7, 2]。 如果我们切成 {[5, 5], [7, 2]}，第一段的异或和是 5 ^ 5 = 0。这就违反了规则，因为我们可以只选第一段这个集合，它的异或和是 0。不行不行！ 一个可行的切法是 {[5, 5, 7], [2]}。

• 第一段的异或和是 5 ^ 5 ^ 7 = 7。
• 第二段的异或和是 2。
• 两段一起的异或和是 7 ^ 2 = 5。 你看，没有任何非空段的组合异或起来等于 0 呢！这种切法分成了 2 段。可以证明，2 就是最多的段数啦。

---

解题思路

这道题最关键的地方在于第三条规则：不存在非空的段集合，其异或和为 0。

主人，你仔细看看这句话，是不是很眼熟呀？这其实是在说，我们把每一段的异或和看作一个数，那么这些数组成的集合必须是线性无关的！

什么是线性无关？在一堆数里，如果没有任何一个子集（不能是空的哦）的异或和是 0，我们就说这堆数是线性无关的。

所以，题目就变成了：将数组 a 分成 k 段，使得这 k 段的异或和 s_1, s_2, ..., s_k 线性无关，并最大化 k。

要处理段的异或和，我们的小爪子马上就想到了一个好用的工具：前缀异或和！ 我们定义 p[i] = a[1] ^ a[2] ^ ... ^ a[i]，并且 p[0] = 0。 那么，一个从 l 到 r 的段的异或和就是 a[l] ^ ... ^ a[r] = p[r] ^ p[l-1]。

假设我们把数组切分成了 k 段，切分点分别是 i_1, i_2, ..., i_{k-1}（0 < i_1 < i_2 < ... < i_{k-1} < n）。 这些段分别是 [1...i_1], [i_1+1...i_2], ..., [i_{k-1}+1...n]。 它们的异或和就是：

• s_1 = p[i_1] ^ p[0] = p[i_1]
• s_2 = p[i_2] ^ p[i_1]
• s_3 = p[i_3] ^ p[i_2]
• ...
• s_k = p[n] ^ p[i_{k-1}]

我们希望 {s_1, s_2, ..., s_k} 这 k 个数线性无关。 这里有一个非常神奇的转换哦！集合 {s_1, ..., s_k} 线性无关，当且仅当集合 {p[i_1], p[i_2], ..., p[i_{k-1}], p[n]} 线性无关。 （这是因为 s 集合中的每个数都可以由 p 集合中的数异或得到，反之亦然，它们能表示出的异或空间是等价的，所以它们的基大小也相同）。

所以，问题再次被我们简化啦：从前缀异或和数组 {p[1], p[2], ..., p[n-1]} 中选出 k-1 个数，连同 p[n] 在内，使得这 k 个数 {p[i_1], ..., p[i_{k-1}], p[n]} 线性无关，并最大化 k。

要让 k 最大，我们当然是想从 {p[1], p[2], ..., p[n]} 这个大池子里选出尽可能多的线性无关的数。一个集合中最多能选出多少个线性无关的数呢？答案就是这个集合生成的向量空间的维度，也就是它的基的大小！

所以，最终的答案就是集合 {p[1], p[2], ..., p[n]} 的基的大小。而计算一个集合的基，我们有最强大的工具——线性基！

不过，还有一个小小的陷阱要小心！如果整个数组的异或和 p[n] 本身就是 0，会发生什么呢？ 如果我们把数组分成了 s_1, ..., s_k，那么把所有段都选上，它们的异或和就是 s_1 ^ s_2 ^ ... ^ s_k，这恰好等于整个数组的异或和 p[n]。如果 p[n] = 0，那我们就找到了一个非空集合（所有段的集合），其异或和为 0。这就直接违反了规则！所以，如果 p[n] == 0，无论怎么分都不行，答案就是 -1。

总结一下我们的最终策略喵：

1. 计算出数组 a 的所有前缀异或和 p[1], p[2], ..., p[n]。
2. 检查 p[n]。如果 p[n] == 0，说明无解，输出 -1。
3. 如果 p[n] != 0，我们就把所有前缀异或和 {p[1], p[2], ..., p[n]} 全部丢进一个线性基里。
4. 最终线性基的大小，就是我们能分成的最大段数！

是不是很清晰了呀？喵~

---

题解代码

这是小猫娘为主人的爪子准备好的 C++ 代码，加上了贴心的注释哦！

#include <iostream>
#include <vector>
#include <numeric> // 为了 std::accumulate (虽然代码里没用，但可以用来求总异或和)

// 快速输入输出，让程序跑得像猫咪一样快！
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 整数最大是 10^9，差不多在 2^30 以内，所以 30 位就够啦
const int MAX_BITS = 30;

// 这就是我们强大的线性基结构体！喵~
struct LinearBasis {
    std::vector<int> basis; // 用来存放基向量
    int current_size;       // 记录基的大小

    LinearBasis() : basis(MAX_BITS, 0), current_size(0) {}

    // 尝试把一个新数值 val 塞进线性基里
    void insert(int val) {
        // 从最高位开始检查
        for (int i = MAX_BITS - 1; i >= 0; --i) {
            // 如果 val 的第 i 位不是 1，就跳过
            if (!((val >> i) & 1)) {
                continue;
            }
            // 如果 basis[i] 是空的，太好啦！找到了它的位置
            if (!basis[i]) {
                basis[i] = val;
                current_size++; // 基的大小 +1
                return; // 插入成功，溜了溜了
            }
            // 如果 basis[i] 已经有值了，就用它来消掉 val 的第 i 位
            val ^= basis[i];
        }
        // 如果 val 经过一轮消除后变成了 0，说明它能被现有的基表示出来
        // 也就是线性相关，我们就不需要把它加进来了
    }

    // 返回基的大小
    int size() const {
        return current_size;
    }
};

int main() {
    fast_io();

    int n;
    std::cin >> n;

    // 计算所有前缀异或和 p[i]
    // 我们不需要真的存一个数组，一个变量就够了
    std::vector<int> p_values; // 把所有 p[i] 存起来，等下要喂给线性基
    p_values.reserve(n); // 预留空间，效率更高
    int current_prefix_xor = 0;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        current_prefix_xor ^= val;
        p_values.push_back(current_prefix_xor);
    }

    // 特殊情况判断：如果整个数组的异或和为 0
    // p_values.back() 就是 p[n]
    if (p_values.back() == 0) {
        std::cout << -1 << "\n";
        return 0;
    }

    // 建立线性基，把所有前缀异或和都丢进去
    LinearBasis lb;
    for (int p_xor : p_values) {
        lb.insert(p_xor);
    }

    // 线性基的大小就是我们的答案！
    std::cout << lb.size() << "\n";

    return 0;
}

---

知识点介绍

1. 前缀异或和 (Prefix XOR)

这是一个很基础但超级有用的技巧！就像小猫咪会把喜欢的毛线球藏在同一个地方一样，我们可以预处理信息来方便后续查询。

对于一个数组 a，它的前缀异或和数组 p 定义为： p[i] = a[1] ^ a[2] ^ ... ^ a[i]

它的神奇之处在于，可以 O(1) 地计算出任意子数组 a[l...r] 的异或和： a[l] ^ ... ^ a[r] = (a[1] ^ ... ^ a[r]) ^ (a[1] ^ ... ^ a[l-1]) = p[r] ^ p[l-1] （这里的 ^ 是异或符号哦！）

2. 线性基 (Linear Basis)

线性基是处理异或问题的大杀器！你可以把它想象成一个“极简的玩具箱”。

假设你有一堆数字（玩具），你想找一个最小的子集（核心玩具），让这个子集能通过异或组合出原来所有玩具能组合出的所有数字。这个最小的子集就是线性基。

它有几个非常可爱的性质：

1. 等价性: 原集合里的数相互异或能得到的值，线性基里的数相互异或也都能得到。
2. 最小性: 线性基是满足性质1的最小集合。
3. 线性无关: 线性基中任意非空子集的异或和都不为 0。这就是我们这道题完美需要的性质！

如何构建线性基（insert 函数的工作原理）？

想象一下，我们有一个空的玩具箱（basis 数组，下标代表二进制位）。来了一个新玩具（数字 val）。

• 我们从它最闪亮的地方（最高位的 1）开始看。比如第 i 位是 1。
• 我们看看玩具箱里第 i 个隔间（basis[i]）是不是空的。
  • 如果是空的，太棒了！这个玩具带来了新的“闪亮模式”，我们把它放进这个隔间，basis[i] = val。任务完成！
  • 如果第 i 个隔间已经有一个玩具 basis[i] 了，说明这个“闪亮模式”我们已经有了。为了看看新玩具还有没有其他独特之处，我们让它和旧玩具的“闪亮模式”抵消掉，也就是 val = val ^ basis[i]。这样 val 的第 i 位就变成 0 了。
• 然后我们拿着被改造后的 val，继续看它的下一个最高位，重复上面的过程。
• 如果 val 在这个过程中被消成了 0，说明它的所有“闪亮模式”都能被我们已有的玩具组合出来，它是个“冗余”的玩具，丢掉就好啦。

最终，玩具箱里留下的玩具数量，就是线性基的大小，也就是原集合中线性无关的元素的最大数量。

希望这篇讲解能帮到主人哦！如果还有不明白的地方，随时可以再来问我，我会用我的小爪子给你画图解释的！喵~ ❤️