【GESP】C++五级真题（前缀和思想考点） luogu-P14074 [GESP202509 五级] 有趣的数字和

GESP C++ 2025年9月五级真题，前缀和考点，题目难度⭐⭐⭐☆☆，五级来说难度适中。洛谷难度等级普及/提高−

luogu-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。

---

题目分析

这是一道典型的数位 DP（Digit DP）题目。

1. 问题转化

题目要求计算区间 $[l, r]$ 内所有二进制表示中含有奇数个 $1$ 的整数之和。 根据前缀和的思想，区间 $[l, r]$ 的答案可以转化为： \(\text{Answer} = \text{solve}(r) - \text{solve}(l-1)\) 其中 $\text{solve}(n)$ 表示在区间 $[1, n]$ 中满足条件的整数之和。

2. 暴力法分析

最直接的方法是遍历 $l$ 到 $r$ 之间的每一个数，统计其二进制中 $1$ 的个数。如果 $1$ 的个数是奇数，则累加该数。 对于每个数，统计 $1$ 的个数需要 $O(\log n)$ 的时间。总时间复杂度为 $O((r - l) \log r)$。

题目给出的数据范围是 $l, r \le 10^9$。如果 $r - l$ 很大（例如接近 $10^9$），总运算量将达到 $10^{10}$ 级别，远远超出一般评测机 1 秒约 $10^8$ 次运算的限制，因此暴力法只能通过部分小数据测试点，必定会超时。

3. 数位 DP 解法：手把手教你“试填法”

数位 DP 听起来很高大上，其实核心逻辑就是一位一位地试填数字。我们可以把它想象成在一个二叉树上走迷宫。

一、 核心思想：二叉树上的抉择

假设我们要找 $[0, n]$ 之间符合条件的数。把 $n$ 转为二进制，比如 $n = 6$ (二进制 110)。我们从最高位（第 2 位）开始，每一位都有两个选择：填 0 或者填 1。这就像走迷宫，每次遇到岔路口（0 或 1），我们都要做一个决定，直到走到最底层（第 0 位）。

二、 关键逻辑详解：Limit（上界限制）是什么？

这是数位 DP 中最难理解也最精妙的地方。我们用 $n=6$ (二进制 110) 来举例演示。

我们要构造一个数 $x$，要求 $x \le n$。

第 2 位（最高位）：$n$ 的第 2 位是 1。

• 选择填 0：构成的数是 0??。不管后面问号填什么（最大是 011 即 3），一定比 110 (6) 小。
  • -> 限制解除！从下一位开始，想填 0 就填 0，想填 1 就填 1，完全自由。
• 选择填 1：构成的数是 1??。这就“顶格”了，贴着 $n$ 走了。
  • -> 限制继续！下一位不能随便填，最大只能填 $n$ 的下一位。

第 1 位：

• 如果在上一位我们填了 0（限制已解除），这一位随便填 0 或 1。
• 如果在上一位我们填了 1（限制仍在），$n$ 的第 1 位是 1。
  • 我们填 0 -> 变成 10?，比 110 小，限制解除。
  • 我们填 1 -> 变成 11?，又顶格了，限制继续。

通俗口诀：

“只要这一位填的小于 $n$ 对应的位，后面就自由了；如果这一位填的和 $n$ 一样，后面还得受限制”

三、 递归函数设计 (DFS)

为了让程序自动完成这个过程，我们设计一个递归函数 dfs。它需要三个关键参数：

（1） pos (我在哪？)

• 告诉函数当前正在处理第几位。比如 pos=2 表示在处理最高位。
• 当 pos < 0 时，说明所有位都填完了，我们可以根据结果判断这个数是不是“有趣的”。

（2） parity (现在的状态是啥？)

• 题目只关心 1 的个数是奇数。
• 我们带个记号 parity 往下走。
• 遇到 0，记号不变；遇到 1，记号翻转（0变1，1变0）。
• 走到尽头时，看一眼 parity 是 1 还是 0，就知道这个数合不合格。

（3） limit (还能随便填吗？)

• 就是上面解释的“上界限制”。
• true 代表受限，只能填到 $n$ 当前位的数字；false 代表自由，可以填 0 或 1。

四、 进阶：不仅要数数，还要算和

普通的数位 DP 只需要返回“有多少个满足条件的数”。但这道题要求“所有满足条件的数的和”。这需要一点数学推导。

场景模拟：

假设当前在第 pos 位，我们决定填数字 d（d 是 0 或 1）。然后递归调用下一层，下一层告诉我们：“在你的这个决定下，后面有 cnt 个合法的数，它们后面的部分加起来和是 sum。”

那么，当前这一位填的 d 对总和的贡献是多少呢？

• 当前位的价值：当前位是第 pos 位，填数字 d 代表的数值是 $d \times 2^{pos}$。
• 出现了多少次：这个前缀会拼上 cnt 种不同的后缀，所以这个数值出现了 cnt 次。
• 公式：

\(\text{当前位贡献} = (d \times 2^{pos}) \times cnt\) \(\text{当前分支总和} = \text{当前位贡献} + \text{后缀累加和(sum)}\)

五、 总结

• 拆分：把 $n$ 拆成二进制数组。
• 搜索：从最高位开始 dfs，维护 limit 和 parity。
• 记忆：如果当前状态没有限制 (!limit)，就把结果记下来，下次直接用。

时间复杂度

• 每个位上只有 0 和 1 两种选择，所以状态数量是 $O(2 \times \log n) = O(\log n)$。
• 每个状态的计算量是 $O(1)$，因为只需要简单的位运算和乘法。

所以，整体时间复杂度是 $O(\log n)$。二进制位最多约 30-60 位，状态数量极少，计算非常高效。

---

示例代码

/*
 * P14074 [GESP202509 五级] 有趣的数字和
 * 题目要求：计算 [l, r] 区间内二进制表示中包含奇数个 1 的整数之和。
 * 算法：数位 DP
 */

#include <iostream>

typedef long long ll;

// Result 结构体用于存储 DP 的结果
struct Result {
    ll cnt;  // 满足条件的数的个数
    ll sum;  // 满足条件的数的和
};

// digits 存储数字 n 的二进制每一位，digits[0] 是最低位
int digits[40];
// memo 用于记忆化搜索，memo[pos][parity] 表示处理到第 pos 位，当前 1
// 的个数奇偶性为 parity 时的结果 parity = 0 表示偶数个 1，parity = 1 表示奇数个
// 1
Result memo[40][2];

// dfs 函数进行数位 DP
// pos: 当前处理的二进制位（从高位到低位）
// parity: 当前已经确定的高位中 1 的个数的奇偶性（0 为偶，1 为奇）
// limit: 是否受到上界限制。true 表示当前位只能取 0 到 digits[pos]，false
// 表示可以取 0 或 1
Result dfs(int pos, int parity, bool limit) {
    // 递归边界：处理完所有位（pos < 0）
    if (pos == -1) {
        // 如果最终 1 的个数是奇数（parity == 1），则这是一个“有趣的数”
        if (parity == 1) {
            return {1, 0};  // 返回个数 1，和 0（因为具体的数值在回溯时计算）
        } else {
            return {0, 0};  // 不是有趣的数
        }
    }
    // 记忆化搜索：如果不再受限且已经计算过，直接返回结果
    if (!limit && memo[pos][parity].cnt != -1) {
        return memo[pos][parity];
    }

    // 确定当前位的枚举上限
    int up = limit ? digits[pos] : 1;
    Result res = {0, 0};

    // 枚举当前位可能的取值 i (0 或 1)
    for (int i = 0; i <= up; i++) {
        // 递归处理下一位
        // pos - 1: 下一位
        // parity ^ i: 更新奇偶性。如果 i=0，奇偶性不变；如果 i=1，奇偶性翻转
        // limit && (i == up):
        // 更新限制状态。只有当前受限且选了上限，下一位才继续受限
        Result sub = dfs(pos - 1, parity ^ i, limit && (i == up));

        // 累加符合条件的数的个数
        res.cnt += sub.cnt;

        // 计算当前位对和的贡献
        // 当前位的值是 i * 2^pos
        ll cur_val = (ll)i << pos;
        // 当前位贡献的总和 = 当前位的值 * 后续满足条件的数的个数 +
        // 后续满足条件的数的和
        res.sum += sub.sum + cur_val * sub.cnt;
    }

    // 如果不受限，记录结果到 memo
    if (!limit) {
        memo[pos][parity] = res;
    }

    return res;
}

// solve 函数计算 [0, n] 范围内有趣的数的和
ll solve(ll n) {
    int len = 0;
    // 将 n 转换为二进制存入 digits 数组
    while (n) {
        digits[len] = n & 1;
        n >>= 1;
        len++;
    }
    // 初始化 memo 数组为 -1，表示未计算
    for (int i = 0; i < 40; i++) {
        for (int j = 0; j < 2; j++) {
            memo[i][j].cnt = -1;
        }
    }
    // 从最高位开始 DFS
    // 初始 limit 为 true，因为最高位受 n 的限制
    // 初始 parity 为 0，因为还没选任何 1
    return dfs(len - 1, 0, true).sum;
}

int main() {
    // 定义左右边界 l 和 r，使用 long long 防止溢出
    ll l, r;
    std::cin >> l >> r;
    // 利用前缀和思想：[l, r] 的和 = solve(r) - solve(l - 1)
    std::cout << solve(r) - solve(l - 1) << std::endl;
    return 0;
}

同样，本题之所以调低时间限制，就是因为很显然存在暴力模拟算法，可以直接算出答案，显然违反了出题者本意。示例代码如下：

#include <iostream>

typedef long long ll;

int main() {
    // 定义左右边界 l 和 r，使用 long long 防止溢出
    ll l, r;
    std::cin >> l >> r;

    // ans 用于存储区间 [l, r] 内所有“有趣的整数”之和
    ll ans = 0;

    // 遍历区间 [l, r] 中的每一个整数 i
    // 时间复杂度分析：
    // 外层循环执行 (r - l + 1) 次。
    // 内层 while 循环每次处理一个整数，执行次数为该整数的二进制位数，约为
    // log2(r)。 对于 r <= 10^9，log2(r) 约为 30。 总时间复杂度为 O((r - l) *
    // log r)。 当 r - l 很大（如 10^9）时，运算量约为 3 * 10^10，会超出通常 1
    // 秒（约 10^8 次运算）的时间限制，导致超时 (TLE)。
    // 该算法只能通过小数据范围的测试点 (40% 数据)。
    for (ll i = l; i <= r; i++) {
        int tmp = 0;  // tmp 用于记录当前整数 i 的二进制表示中 1 的个数
        ll num = i;   // 复制 i 到 num，以免修改循环变量 i

        // 计算 num 的二进制表示中 1 的个数
        while (num > 0) {
            // 如果 num 的最低位是 1 (即 num 是奇数)
            if (num & 1) {
                tmp++;
            }
            // 将 num 右移一位，相当于除以 2
            num >>= 1;
        }

        // 如果 1 的个数是奇数，则认为该整数是“有趣的”
        if (tmp % 2 == 1) {
            ans += i;  // 将该整数累加到总和 ans 中
        }
    }

    // 输出最终结果
    std::cout << ans << std::endl;
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号