萌新求问，这道题有复杂度更低的解法吗

stringdp100005 · 2025 年2 月 25 日 12:22

求 \sum\limits_{l=1}^n\sum\limits_{r=l}^n\bigoplus\limits_{i=l}^r i 。
我只会线性做法，不知道有没有 O(1) 的。

stringdp100005 · 2025 年2 月 25 日 12:23

不是发个啥 qp 啊，水帖水疯了是吧

金杭东 · 2025 年2 月 25 日 12:23

我只会N^2

stringdp100005 · 2025 年2 月 25 日 12:25

想打个表找找规律

金杭东 · 2025 年2 月 25 日 12:26

好卡，呜呜呜

stringdp100005 · 2025 年2 月 25 日 12:30

DeepSeek 的线性做法：
（发 AI 代码违规吗）

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long result = 0;
    for (int k = 0; k <= 30; ++k) {
        int count0 = 1; // 初始前缀异或为0的情况有1次（prefix[0]）
        int count1 = 0;
        int current_xor = 0;
        long long cnt = 0;
        for (int i = 1; i <= n; ++i) {
            int bit = (i >> k) & 1;
            current_xor ^= bit;
            if (current_xor) {
                cnt += count0;
            } else {
                cnt += count1;
            }
            if (current_xor) {
                count1++;
            } else {
                count0++;
            }
        }
        result += cnt * (1LL << k);
    }
    cout << result << endl;
    return 0;
}

我命由我不由天 · 2025 年2 月 26 日 05:46

@stringdp100005 能AC就违规