P14074 [GESP202509 五级] 有趣的数字和

题目背景

为保证只有时间复杂度合理的算法通过本题，本题时限下调。

题目描述

如果一个正整数的二进制表示包含奇数个 $1$，那么小 A 就会认为这个正整数是有趣的。

例如，$7$ 的二进制表示为 $(111{)}_2$，包含 $1$ 的个数为 $3$ 个，所以 $7$ 是有趣的。但是 $9=(1001{)}_2$ 包含 $2$ 个 $1$，所以 $9$ 不是有趣的。

给定正整数 $l,r$，请你统计满足 $l\le n\le r$ 的有趣的整数 $n$ 之和。

输入格式

一行，两个正整数 $l,r$，表示给定的正整数。

输出格式

一行，一个正整数，表示 $l,r$ 之间有趣的整数之和。

输入输出样例 #1

输入 #1

3 8

输出 #1

19

输入输出样例 #2

输入 #2

65 36248

输出 #2

328505490

说明/提示

【数据范围】

对于 $40\%$ 的测试点，保证 $1\le l\le r\le 10^4$。

对于另外 $30\%$ 的测试点，保证 $l=1$ 并且 $r=2^k-1$，其中 $k$ 是大于 $1$ 的正整数。

对于所有测试点，保证 $1\le l\le r\le 10^9$。

【提示】

由于本题的数据范围较大，整数类型请使用 long long。

解析

40%的解法

对于前40%的数据，直接模拟即可，详见代码：

#include <bits/stdc++.h>
using namespace std;
int l,r;
long long sum=0;
bool f(int x){//判断x的二进制中是否奇数个1
    int cnt=0;
    while(x>0){
        cnt+=x%2;
        x/=2;
    }
    return cnt%2;
}
int main() {
    cin>>l>>r;
    for(int i=l;i<=r;i++){
        if (f(i)){
            sum+=i;
        }
    }
    cout<<sum;
    return 0;
}

70%的解法

对于另外30%，相当于二进制的1 到11111（k个1）中奇数个1的和，在完整区间 [0, 2^k-1] 中，二进制中1的个数为奇数和偶数的数各占一半，答案即总和的一半，结合前边40%的解法，70%分数的解法如下：

#include <bits/stdc++.h>
using namespace std;
long long l,r;
long long sum=0;
bool f(int x){//判断x的二进制中是否奇数个1
    int cnt=0;
    while(x>0){
        cnt+=x%2;
        x/=2;
    }
    return cnt%2;
}
int main() {
    cin>>l>>r;
    if (r<=1e4){
        for(int i=l;i<=r;i++){
            if (f(i)){
                sum+=i;
            }
        }
        cout<<sum;
        return 0;
    }
    cout<<(r+1)*r/4;//计算1到r（2^k）之间所有数和的一半
    return 0;
}

正解：通过递归将区间划分为 [0, 2^k-1] 和剩余部分，利用二进制数的性质来计算二进制中1的个数为奇数的数之和。

#include <algorithm>
#include <cstdio>
using namespace std;

int l, r;
long long ans;

/**
 * 计算区间 [0, n] 中满足特定popcount奇偶性的数的个数和总和
 * @param n 区间上限
 * @param p 目标popcount奇偶性 (0=偶数个1, 1=奇数个1)
 * @return pair<个数, 总和>
 */
pair<int, long long> cal2(int n, int p) {
    // 特殊情况处理：n = 0
    if (n == 0) {
        // 只有数字0，popcount=0（偶数）
        // 如果目标是偶数(p=0)，有1个数；如果是奇数(p=1)，有0个数
        return {1 - p, 0};  // 个数=1-p，总和=0
    }
    
    // 特殊情况处理：n = 1
    if (n == 1) {
        // 数字0(popcount=0)和1(popcount=1)
        // 如果目标是奇数(p=1)，只有数字1符合，返回{1, 1}
        // 如果目标是偶数(p=0)，只有数字0符合，返回{1, 0}
        return {1, p};  // 个数=1，总和=p（p=1时总和=1，p=0时总和=0）
    }
    
    // 一般情况：n > 1
    // 在区间[0,n]中，popcount为奇数和偶数的数各占约一半
    // 个数 = (n+1)/2（向上取整）
    // 总和 = n*(n+1)/4（所有数总和的一半，因为奇偶分布均匀）
    return {(n + 1) / 2, 1ll * n * (n + 1) / 4};
}

/**
 * 递归计算区间 [0, n] 中满足特定popcount奇偶性的数的个数和总和
 * @param n 区间上限
 * @param p 目标popcount奇偶性 (0=偶数个1, 1=奇数个1)
 * @return pair<个数, 总和>
 */
pair<int, long long> cal(int n, int p) {
    // 基本情况：n很小的时候直接计算
    if (n <= 1) {
        return cal2(n, p);
    }
    
    // 找到小于等于n的最大2的幂
    // __builtin_clz(n) 计算n的二进制前导0的个数
    // 31 - __builtin_clz(n) 得到最高位的位置
    long long x = 1ll << (31 - __builtin_clz(n));
    
    // 将区间 [0, n] 划分为两部分：
    // 第一部分：[0, x-1]（完整的二进制区间）
    // 第二部分：[x, n]（剩余区间）
    
    // 计算第一部分：完整的二进制区间 [0, x-1]
    auto left_part = cal2(x - 1, p);
    
    // 计算第二部分：[x, n] = [0, n-x] 每个数加上x
    // 由于x是2的幂（二进制形式为100...0），加上x后popcount奇偶性翻转
    // 所以第二部分的popcount目标变为 1-p
    auto right_part = cal(n - x, 1 - p);
    
    // 合并结果：
    // 总个数 = 第一部分个数 + 第二部分个数
    // 总和 = 第一部分总和 + 第二部分总和 + x * 第二部分个数
    // （因为第二部分每个数都加了x，所以总和要额外加上x乘以个数）
    return {left_part.first + right_part.first, 
            left_part.second + right_part.second + x * right_part.first};
}

int main() {
    // 读取输入区间 [l, r]
    scanf("%d%d", &l, &r);
    
    // 计算 [l, r] 区间内popcount为奇数的数之和
    // 使用前缀和思想：F(l, r) = F(0, r) - F(0, l-1)
    
    // 计算 [0, l-1] 中popcount为奇数的数的和，并从结果中减去
    ans -= cal(l - 1, 1).second;
    
    // 计算 [0, r] 中popcount为奇数的数的和，加到结果中
    ans += cal(r, 1).second;
    
    // 输出最终结果
    printf("%lld\n", ans);
    
    return 0;
}

记忆化搜索的解法

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

// dp[pos][tight][odd] = {count, sum}
//pos: 当前处理的二进制位位置（从高位到低位）
//tight: 是否紧贴边界（之前的选择是否与N的二进制表示完全一致）
//odd: 当前已选择位的popcount奇偶性（0表示偶数，1表示奇数）
pair<ll, ll> dp[35][2][2];
vector<int> digits;
int len;

pair<ll, ll> dfs(int pos, int tight, int odd) {
    if (pos == len) {
        // 到达最后一位，如果当前popcount为奇数，返回计数1，和0（和已经在过程中计算）
        if (odd == 1) return {1, 0};
        else return {0, 0};
    }
    if (dp[pos][tight][odd].first != -1) return dp[pos][tight][odd];
    
    ll cnt = 0, sum = 0;
    int up = tight ? digits[pos] : 1;  // 如果紧贴边界，最高只能取到digits[pos]，否则可以取到1
    
    for (int d = 0; d <= up; d++) {
        auto [c, s] = dfs(pos + 1, tight && (d == up), odd ^ (d == 1));
        cnt += c;
        sum += s;
        if (d == 1) {
            // 当前位为1，贡献 = 1 << (len - pos - 1) 乘以这个分支的数的个数
            ll bit_val = (1LL << (len - pos - 1));
            sum += c * bit_val;
        }
    }
    return dp[pos][tight][odd] = {cnt, sum};
}
//求1到N中二进制1的个数为奇数的数的和
ll F(ll N) {
    if (N == 0) return 0;
    
    // 将N转换为二进制表示
    digits.clear();
    ll x = N;
    while (x) {
        digits.push_back(x & 1);
        x >>= 1;
    }
    reverse(digits.begin(), digits.end());
    len = digits.size();
    
    // 初始化DP数组
    memset(dp, -1, sizeof dp);
    
    auto [cnt, sum] = dfs(0, 1, 0);
    return sum;
}

int main() {
    ll l, r;
    cin >> l >> r;
    
    // 计算F(r) - F(l-1)
    ll ans = F(r) - F(l - 1);
    cout << ans << endl;
    
    return 0;
}