题解 | #小苯的美丽区间#

题目链接

REAL738 小苯的美丽区间

题目描述

小苯定义一个数 $x$ 是美丽数，当且仅当：将 $x$ 不停除以 2，直到结果 $x'$ 不整除 2 时停止，此时 $x'$ 恰好等于 1。

如果一个数是美丽数，其美丽值为：以上操作中除以 2 的次数。
否则，其美丽值为 0。

现在给定一个长度为 $n$ 的数组 $a$ ，请你计算所有连续子数组的和的美丽值之和。

形式化地，记数字 $x$ 的美丽值为 $\text{beauty}(x)$ ，请你求出 $\sum_{i=1}^{n} \sum_{j=i}^{n} \text{beauty}(\sum_{k=i}^{j} a_k)$ 。

思路分析

1. 解读“美丽数”和“美丽值”

美丽数：一个数 $x$ 不停地除以2，直到结果为奇数。如果这个奇数是1，那么 $x$ 就是美丽数。这等价于说，一个数是美丽数，当且仅当它是2的整数次幂（ $x = 2^k, k \ge 0$ ）。
美丽值：如果一个数 $x = 2^k$ 是美丽数，其美丽值为 $k$ 。否则，美丽值为0。这个 $k$ 实际上就是 $\log_2(x)$ ，也等于 $x$ 的二进制表示中末尾0的个数。

2. 问题转换：从子数组到前缀和

我们的目标是计算所有子数组的和的美丽值。直接枚举所有子数组（ $O(N^2)$ 个）并求和（ $O(N)$ ），总复杂度是 $O(N^3)$ ，无法接受。

我们可以利用前缀和来优化子数组求和。设前缀和数组 P，其中 $P[k] = \sum_{i=0}^{k-1} a_i$ ，并且我们定义 $P[0]=0$ 。那么，子数组 $a[i..j]$ (0-indexed) 的和就是 $P[j+1] - P[i]$ 。

现在问题变为：计算所有满足 $0 \le i \le j < n$ 的数对 $(i, j)$ ，对它们对应的和 $S = P[j+1] - P[i]$ 求美丽值，并累加。

由于美丽值只对2的幂次有意义，我们只需要关心那些和恰好是 $2^k$ 的子数组。也就是说，我们需要找到所有满足 $P[j+1] - P[i] = 2^k$ 的数对 $(i, j)$ ，对于每个这样的数对，其贡献的美丽值为 $k$ 。

3. 核心算法：前缀和 + 哈希表

我们可以将条件 $P[j+1] - P[i] = 2^k$ 变形为 $P[i] = P[j+1] - 2^k$ 。

这个形式启发我们使用一个高效的算法：当我们遍历数组，计算到前缀和 $P[j+1]$ 时，我们不再回头去找符合条件的 $i$ ，而是向前看：我们需要知道在 $j+1$ 之前，有多少个前缀和 $P[i]$ 等于 $P[j+1] - 2^k$ ？

我们可以用一个**哈希表（Map/Dictionary）**来动态地记录到目前为止出现过的所有前缀和及其出现次数。

算法步骤：

初始化总美丽值 total_beauty = 0。
初始化一个哈希表 counts，并放入 {0: 1}，表示数值为0的前缀和（即 $P[0]$ ）已经出现过1次。
初始化当前前缀和 current_sum = 0。
遍历数组 $a$ 的每个元素 $a_i$ ：

a. 更新 current_sum = current_sum + a_i。这相当于计算了 $P[i+1]$ 。

b. 对于这个新的 current_sum，我们检查它是否能与之前的前缀和构成一个和为2的幂的子数组。我们遍历所有可能的2的幂次 $2^k$ （ $k$ 从0开始）。

i. 计算 target = current_sum - 2^k。

ii. 如果 target 在哈希表 counts 中存在，说明我们找到了 counts[target] 个子数组，它们的和都是 $2^k$ 。

iii. 这些子数组的美丽值都是 $k$ 。我们将 $k \times \text{counts}[\text{target}]$ 累加到 total_beauty 中。

c. 将当前的 current_sum 存入哈希表：counts[current_sum]++。
遍历结束后，total_beauty 就是最终答案。

最大可能的数组和约为 $2 \cdot 10^5 \times 10^9 = 2 \cdot 10^{14}$ 。 $2^{50}$ 约等于 $1.12 \cdot 10^{15}$ ，所以 $k$ 的取值范围大约在0到50之间，这是一个很小的常数，因此内层循环是可接受的。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>

using namespace std;

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

    map<long long, int> counts;
    counts[0] = 1;
    long long current_sum = 0;
    long long total_beauty = 0;

    for (int i = 0; i < n; ++i) {
        current_sum += a[i];
        for (int p = 0; p < 60; ++p) {
            long long power_of_2 = 1LL << p;
            long long target = current_sum - power_of_2;
            if (counts.count(target)) {
                total_beauty += (long long)p * counts[target];
            }
        }
        counts[current_sum]++;
    }
    cout << total_beauty << endl;
}

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

import java.util.HashMap;
import java.util.Map;
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();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Map<Long, Integer> counts = new HashMap<>();
        counts.put(0L, 1);
        long currentSum = 0;
        long totalBeauty = 0;

        for (int i = 0; i < n; i++) {
            currentSum += a[i];
            for (int p = 0; p < 60; p++) {
                long powerOf2 = 1L << p;
                long target = currentSum - powerOf2;
                if (counts.containsKey(target)) {
                    totalBeauty += (long) p * counts.get(target);
                }
            }
            counts.put(currentSum, counts.getOrDefault(currentSum, 0) + 1);
        }
        System.out.println(totalBeauty);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    counts = {0: 1}
    current_sum = 0
    total_beauty = 0
    
    for x in a:
        current_sum += x
        for p in range(60): # 2^60 is large enough for constraints
            power_of_2 = 1 << p
            if power_of_2 > current_sum:
                break
            target = current_sum - power_of_2
            if target in counts:
                total_beauty += p * counts[target]
        
        counts[current_sum] = counts.get(current_sum, 0) + 1
        
    print(total_beauty)

def main():
    try:
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

main()

算法及复杂度

算法：前缀和 + 哈希表
时间复杂度： $O(N \cdot \log S_{max})$ ，其中 $N$ 是数组长度， $S_{max}$ 是数组可能的最大前缀和。由于 $S_{max}$ 可以很大（约 $2 \cdot 10^{14}$ ）， $\log_2 S_{max}$ 大约是 50-60，可以看作一个常数。因此，总时间复杂度可以认为是 $O(N)$ 。
空间复杂度： $O(N)$ ，在最坏情况下，所有前缀和都不同，哈希表需要存储 $N$ 个键值对。