题意

给定一个长度为 的整数序列，求该序列所有非空子数组的按位或（OR）之和，结果对 取模。

题解

对于与按位运算相关的求和问题，最经典的切入点是拆位计算（贡献法）。

Hint: 二进制下各个数位上的按位或运算是相互独立的。我们可以单独计算每个二进制位在所有子数组中对总和的贡献，最后将每一位的贡献相加求和即可。

考察第 个二进制位，我们需要计算出有多少个非空子数组的按位或结果在该位上是 1。

Hint: 正难则反。如果直接去统计“结果为 1”的子数组数量情况较复杂，我们可以转而统计按位或结果为 0 的子数组数量，再用总子数组数 减去它。

一个子数组的按位或结果在第 位为 0，当且仅当该子数组内的所有元素在第 位上全都是 0。 因此，我们只需遍历原序列，找出所有“第 位为 0”的连续段。假设某连续段的长度为 ，则它能贡献 个在第 位完全由 0 组成的子数组。将所有这种连续段的贡献累加，即为按位或结果在第 位为 0 的子数组总数。

用 减去上述全 0 子数组数量，设得到的差值为 ，那么第 位对最终答案的贡献就是 。枚举所有的二进制位（本题中 ，只需枚举 0 到 29 位），累加即得最终答案。

作为拓展，本题也可以利用按位或的单调性来解决：固定子数组的右端点向左延伸，子数组的按位或值只会单调递增，且由于值域限制最多只有 30 种不同的结果。因此可以动态维护以当前元素结尾的所有可能的或值及其出现次数，扫描时合并相同值即可解决。

复杂度

  • 时间复杂度:
  • 空间复杂度: 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int MOD = 1e9 + 7;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    i64 tot = 1LL * n * (n + 1) / 2;
    i64 ans = 0;

    for (int k = 0; k < 30; ++k) {
        i64 cnt0 = 0, l = 0;
        for (int i = 0; i < n; ++i) {
            if ((a[i] >> k) & 1) {
                cnt0 += l * (l + 1) / 2;
                l = 0;
            } else {
                l++;
            }
        }
        cnt0 += l * (l + 1) / 2;

        i64 cnt1 = tot - cnt0;
        i64 val = (cnt1 % MOD) * ((1LL << k) % MOD) % MOD;
        ans = (ans + val) % MOD;
    }
    cout << ans << '\n';
}

int main() {
    int T; cin >> T;
    while (T--) solve();
}