题解 | #Poi 的新加法（Easy Version）#

本问题是一种特殊二进制加法运算 $f(x, y) = x + y - (x \oplus y)$ 在序列上的链式求值。

1. 问题分析

1.1 运算符性质

首先对运算符进行化简。根据位运算基础恒等式： $x + y = (x \oplus y) + 2(x \text{ AND } y)$ 将该等式代入题目给出的 $f(x, y)$ 定义： $f(x, y) = (x \oplus y) + 2(x \text{ AND } y) - (x \oplus y) = 2(x \text{ AND } y)$ 由此可见，该运算本质上是对两个数进行按位与（AND）操作后，左移一位（LSL 1）。

1.2 链式运算

考察序列 $a_1, a_2, \dots, a_n$ 的运算过程。令 $v_i$ 为前 $i$ 个元素的运算结果：

$v_1 = a_1$
$v_2 = f(v_1, a_2) = 2(a_1 \ \& \ a_2)$
$v_3 = f(v_2, a_3) = 2(v_2 \ \& \ a_3) = 2(2(a_1 \ \& \ a_2) \ \& \ a_3)$ 利用性质 $2A \ \& \ B = 2(A \ \& \ (B \gg 1))$ ，可得： $v_3 = 2^2 \cdot (a_1 \ \& \ a_2 \ \& \ (a_3 \gg 1))$
推广至 $n$ 个元素： $v_n = 2^{n-1} \cdot \left( a_1 \ \& \ a_2 \ \& \ (a_3 \gg 1) \ \& \ (a_4 \gg 2) \ \& \ \dots \ \& \ (a_n \gg (n-2)) \right)$

1.3 边界与约束

题目指出 $a_i < 2^{60}$ ，即 $a_i$ 的最高有效位索引为 59。在上述通项公式中，项 $(a_k \gg (k-2))$ 意味着：

当 $k-2 > 59$ （即 $k > 61$ ）时，对于任何 $a_k < 2^{60}$ ， $(a_k \gg (k-2))$ 必然为 0。
由于链式运算中存在连与（AND）关系，只要 $n > 61$ ，且中间任何一项变为 0，最终结果 $v_n$ 必然为 0。
此外，结果的位宽： $W$ 的最高位索引为 59，左移 $n-1$ 位后，最高位索引为 $59 + n - 1$ 。但注意到由于 $a_n \gg (n-2)$ 的限制，有效位 $s$ 必须满足 $s + n - 2 \le 59$ ，则结果最高位 $s + n - 1 \le 60$ 。因此，结果始终在 64 位无符号整数（uint64_t）范围内。

2. 位运算模拟与常数时间剪枝

基于上述分析，该问题的简单版本（ $q=1, l=1, r=n$ ）可以通过位运算模拟与常数时间剪枝结合的策略解决。

范式选择：线性扫描（Linear Scan）结合位运算优化。
优化技巧：
1. 早期停止：在计算连与过程中，若中间变量 $W$ 变为 0，则可直接判定结果为 0。
2. 规模限制：利用 $n > 61$ 结果必为 0 的特性，将大数组处理退化为常数时间操作。

3. 代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, q;
        cin >> n >> q;
        vector<ll> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];

        while (q--) {
            int l, r;
            cin >> l >> r;
            if (n == 1) {
                cout << a[0] << "\n";
                continue;
            }
            if (n > 61) {
                cout << 0 << "\n";
                continue;
            }
            ll w = a[0] & a[1];
            for (int i = 2; i < n; i++) {
                w = w & (a[i] >> (i - 1));
                if (w == 0)
                    break;
            }
            w <<= (n - 1);
            cout << w << "\n";
        }
    }
}

4. 复杂度分析

时间复杂度

单组测试数据： $O(\min(n, 62))$ 。
总体复杂度： $O(T + \sum \min(n, 62))$ 。

空间复杂度

额外空间： $O(1)$ 。

5. 总结

识别出二进制加法 $f(x, y)$ 是“不完全逻辑进位”操作，等价于 $2(x \ \& \ y)$ 。通过数学归纳法推导出序列的通项表达式后，利用位宽限制将 $O(n)$ 的遍历转化为具有常数上限的逻辑判断。