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

题目链接

题目描述

本题为问题的简单版本。定义一种新的加法运算 $f(x, y)$ ，其运算规则等价于 $(x \text{ AND } y) \ll 1$ 。给定一个长度为 $n$ 的序列 $a$ （其中 $0 \le a_i < 2^{60}$ ），求解 $f(\dots f(f(a_1, a_2), a_3), \dots, a_n)$ 的值。

解题思路

首先，我们需要确定 $f(x, y)$ 的确切定义。题目描述中虽然给出了 $f(x, y) = x+y-(x \oplus y)$ 的公式，但这实际上等价于 $f(x, y) = (x \text{ AND } y) \ll 1$ 。通过题目给出的二进制运算表示例可以确认，我们应该使用后者进行计算。

本题是简单版本，查询固定为整个区间 $[1, n]$ 。我们需要计算 res = a[1]; for i=2..n: res = (res & a[i]) << 1。

当 $n$ 很大时，直接模拟的效率可能不够。我们需要找到一个更快的算法。

关键观察与优化

让我们分析这个迭代运算 res_new = (res_old & a[i]) << 1 的性质：

最低有效位 (LSB) 的变化：<< 1 操作意味着每次运算后，结果的二进制表示末尾都会增加一个 0。只要中间结果不为零，其 LSB 的位置就会严格加一。经过 $k$ 次运算后，结果的 LSB 至少在第 $k$ 位（从0开始计数），即这个数一定是 $2^k$ 的倍数。
最高有效位 (MSB) 的限制：题目中给出 $a_i < 2^{60}$ 。这意味着 res_old & a[i] 的结果不会超过 $2^{60}-1$ ，其 MSB 不会超过第 59 位。经过 << 1 操作后，res_new 的 MSB 最多在第 60 位。因此，运算过程中的任何中间结果和最终结果，其最高有效位都不会超过第60位。

推论

对于区间 $[1, n]$ 的计算，总共需要进行 $n-1$ 次运算。如果最终结果非零，它的 LSB 至少在第 $n-1$ 位，而 MSB 至多在第 60 位。一个非零数必须满足 LSB $\le$ MSB，因此必须有 $n-1 \le 60$ ，即 $n \le 61$ 。

如果 $n > 61$ ，那么 LSB 的理论最小位置将会超过 MSB 的理论最大位置，这是不可能的，除非这个数本身就是 0。

最终算法

对于给定的序列，我们首先检查其长度 $n$ 。
如果 $n > 61$ ，我们可以直接断定结果为 0。
如果 $n \le 61$ ，则执行暴力模拟计算。

由于 $n$ 的最大值为 $10^6$ ，这个剪枝可以极大地优化计算。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, q;
    cin >> n >> q; // q = 1 for easy version
    vector<unsigned long long> a(n); // 使用 unsigned long long 存储 60 位数据
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    int l, r;
    cin >> l >> r; // l=1, r=n for easy version

    if (n > 61) { // 运算次数为 n-1, 如果 n-1 > 60, 结果必为0
        cout << 0 << "\n";
        return;
    }
    
    unsigned long long current_val = a[0];
    for (int j = 1; j < n; ++j) {
        current_val = (current_val & a[j]) << 1;
    }
    cout << current_val << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int q = sc.nextInt(); // q = 1
        long[] a = new long[n]; // Java long is 64-bit, sufficient for 2^60
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        int l = sc.nextInt(); // l = 1
        int r = sc.nextInt(); // r = n

        if (n > 61) { // 运算次数为 n-1, 如果 n-1 > 60, 结果必为0
            System.out.println(0);
            return;
        }

        long currentVal = a[0];
        for (int j = 1; j < n; j++) {
            currentVal = (currentVal & a[j]) << 1;
        }
        System.out.println(currentVal);
    }
}

import sys

def solve():
    n, q = map(int, sys.stdin.readline().split()) # q=1
    a = list(map(int, sys.stdin.readline().split()))
    l, r = map(int, sys.stdin.readline().split()) # l=1, r=n

    # 运算次数为 n-1
    if n > 61: # 如果 n-1 > 60, 结果必为0
        print(0)
        return

    current_val = a[0]
    for i in range(1, n):
        current_val = (current_val & a[i]) << 1
    print(current_val)


t_str = sys.stdin.readline()
if t_str:
    t = int(t_str)
    for _ in range(t):
        solve()

算法及复杂度

算法：位运算 + 剪枝
时间复杂度： $\mathcal{O}(N_{total})$ 。对于每组测试数据，读入 $n$ 个数需要 $\mathcal{O}(n)$ ，后续计算是 $\mathcal{O}(\min(n, 61))$ ，所以总时间由输入规模决定。 $N_{total}$ 是所有测试数据中 $n$ 的总和。
空间复杂度： $\mathcal{O}(\max(n))$ ，用于存储单个测试用例的序列。