题意

给定一个长度为 $n = 2^k$ 的数组 $a$（下标从 $0$ 到 $n-1$）。
每次操作同时将所有元素替换为：

$$a_i = a_i \oplus a_{(i+1) \bmod n}$$

重复操作直到数组全为零。求最少操作次数，若永远不能全零则输出 $-1$。

---

关键观察

$1$. 操作的本质

定义变换 $T$：

$$T(a)_i = a_i \oplus a_{i+1}$$

下标模 $n$，所有 $i$ 同时更新。

这是一个线性变换（在 $\mathbb{F}_2$ 上），且具有很好的结构。

---

$2$. 分治性质

由于 $n$ 是 $2$ 的幂，数组可以不断对半分割。

设当前数组长度为 $len$（$len$ 是 $2$ 的幂）。
考虑将其分成前后两半：

$$L = [a_0, a_1, \dots, a_{len/2-1}], \quad R = [a_{len/2}, a_{len/2+1}, \dots, a_{len-1}] $$

进行一次操作后，观察新数组的前半部分：

$$b_i = a_i \oplus a_{i+len/2} \quad (0 \le i < len/2) $$

这正是 $L$ 和 $R$ 的对应位置异或。

---

$3$. 决策分支

• 如果 $L = R$（即 $a_i = a_{i+len/2}$ 对所有 $i$ 成立），则 $b_i = 0$，此时后半部分在操作后变为 $0$（因为 $a_{i+len/2} \oplus a_{i+len/2+1} = a_i \oplus a_{i+1}$，恰好与前半部分相同）。实际上，此时问题可以缩小一半：只需对 $L$ 继续操作即可，因为 $R$ 会与 $L$ 同步变化。

• 如果 $L \ne R$，则 $b$ 非零，并且可以证明，经过 $len/2$ 次操作后，数组会变为 $[b_0, b_1, \dots, b_{len/2-1}, 0, 0, \dots, 0]$ 的形式（后半全零）。此时问题转化为对长度为 $len/2$ 的数组 $b$ 继续操作，且已经花费了 $len/2$ 步。

---

$4$. 递归/迭代算法

$1$. 若当前数组全为零，返回 $0$。 $2$. 若 $len = 1$：因为 $a_0 = a_0 \oplus a_0 = 0$，一次操作即可，返回 $1$。 $3$. 否则：

• 计算 $b_i = a_i \oplus a_{i+len/2}$（$0 \le i < len/2$）。
• 如果所有 $b_i = 0$（即 $L = R$）：
  • 则只需递归处理长度为 $len/2$ 的 $L$。
• 否则：
  • 花费 $len/2$ 步，然后递归处理长度为 $len/2$ 的 $b$。 $4$. 最后若 $a[0] \ne 0$，还需额外一步（对应 $len=1$ 的情况）。

---

$5$. 正确性说明

• 当 $L = R$ 时，操作 $len/2$ 次后数组会变为全零？不对，实际上每次操作会同时更新 $L$ 和 $R$，但由于 $L=R$，它们始终保持相等，且每次操作相当于对 $L$ 自身做一次变换（因为 $a_{i+len/2} = a_i$）。因此，$L$ 独立演化，$R$ 作为其副本。所以问题规模减半，且无需额外步数。
• 当 $L \ne R$ 时，经过 $len/2$ 次操作后，后半部分变为全零，前半部分变为 $b$。这 $len/2$ 步是必须花费的。
• 最终当长度为 $1$ 时，若该元素非零，则再花 $1$ 步使其变为零。

---

示例验证

样例 $1$

$n=4,\ a=[1,2,1,2]$

• $len=4$：$L=[1,2], R=[1,2]$，相等 → 长度减半为 $2$，$a=[1,2]$
• $len=2$：$L=[1], R=[2]$，不等 → $b=[1\oplus2=3]$，步数 $+=1$，$a=[3]$
• $len=1$：$a[0]=3\ne0$ → 步数 $+=1$ 总步数 $=2$ ✅

样例 $2$

全零 → 输出 $0$ ✅

样例 $3$

$n=1,\ a=[14]$ → 输出 $1$ ✅

样例 $4$

$n=8,\ a=[0,1,2,3,4,5,6,7]$ 模拟可得步数 $=5$ ✅

---

复杂度

每次循环长度减半，总操作 $O(n \log n)$，$n \le 2^{20}$ 可过。

---

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 检查是否全零
    bool allZero = true;
    for (int x : a) {
        if (x != 0) {
            allZero = false;
            break;
        }
    }
    if (allZero) {
        cout << "0\n";
        return 0;
    }
    
    // 特判 n=1
    if (n == 1) {
        cout << "1\n";
        return 0;
    }
    
    int steps = 0;
    int len = n;
    while (len > 1) {
        vector<int> b(len / 2);
        bool equal = true;
        for (int i = 0; i < len / 2; i++) {
            b[i] = a[i] ^ a[i + len / 2];
            if (b[i] != 0) equal = false;
        }
        if (equal) {
            // 两半相等，缩小问题
            a.resize(len / 2);
            len /= 2;
        } else {
            // 需要一次完整操作
            steps += len / 2;
            a = move(b);
            len /= 2;
        }
    }
    
    // 最后还剩一个元素
    if (a[0] != 0) steps++;
    
    cout << steps << "\n";
    
    return 0;
}