形式化题目

在一个棋盘上，第 $i$ 格放有 $2^{i-1}$ 粒米。给定两个正整数 $m$ 和 $n$（$1 \le m, n \le 30$），求从第 $m$ 格至第 $n$ 格的米粒总数。即求 $\sum_{i=\min(m,n)}^{\max(m,n)} 2^{i-1}$。

正解

思路

第一格是 $2^0$，第二格是 $2^1$，第 $i$ 格是 $2^{i-1}$。 计算区间和可以利用等比数列求和公式：前 $k$ 项和 $S_k = \sum_{i=1}^k 2^{i-1} = 2^k - 1$。 那么从第 $a$ 格到第 $b$ 格（假设 $a \le b$）的米粒总数就等于前 $b$ 项和减去前 $a-1$ 项和：

在代码中，我们可以直接通过位运算快速计算 $2^x$，即 1LL << x。

区间端点顺序： 题目中仅保证 $1 \le m, n \le 30$，并没有保证 $m \le n$。在实际数据中存在 $m > n$ 的情况（例如输入 30 25），因此我们需要在计算前调整顺序。C++ 实现中手写一个变量来进行交换，Python 中则利用 min(m, n) 与 max(m, n) 提取较小值与较大值，使区间下界始终不大于上界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 19:46
# update_at: 2026-10-08 19:46

import sys


def solve() -> None:
    """读入 m, n，输出第 m 格到第 n 格的米粒总数（两格编号可能前后颠倒）。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)

    low, high = min(m, n), max(m, n)  # 题面没保证 m <= n，真实数据 gwdml4 就是 30 25
    total = (1 << high) - (1 << (low - 1))  # 区间和公式：2^high - 2^(low-1)
    print(total)


if __name__ == "__main__":
    solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 19:46
 * update_at: 2026-10-08 19:46
 */
// ROJ 8012 国王的米粒：第 i 格放 2^(i-1) 粒米，求第 m 格到第 n 格的米粒总数。
// 等比数列求和：第 a 格到第 b 格（a <= b）共 2^b - 2^(a-1) 粒。
#include <iostream>
using namespace std;

typedef long long ll;

ll m, n; // 两个格子编号，1 <= m, n <= 30；题面没有保证 m <= n

void solve() {
    if (!(cin >> m >> n)) return;

    // 真实数据里存在 m > n（gwdml4 输入 30 25），交换后按小到大求和
    if (m > n) {
        ll tmp = m;
        m = n;
        n = tmp;
    }

    // 2^n - 2^(m-1)：n <= 30，用 1LL 保证移位不丢位数
    ll ans = (1LL << n) - (1LL << (m - 1));
    cout << ans << "\n";
}

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

复杂度

• 时间复杂度：$O(1)$。利用位运算，可以在常数时间内计算出区间和。
• 空间复杂度：$O(1)$。仅使用了几个变量来存储区间端点和结果。

总结

本题表面上是一个单纯的数学求和题，但其实暗藏两个常见的“坑点”：

1. 题目未保证区间起点的先后顺序（$m \le n$） 题面仅规定 $1 \le m, n \le 30$。测试数据 gwdml4.in 的输入就是 30 25。 如果不对 $m$ 和 $n$ 进行交换或取 min/max，按照公式计算 (1<<n) - (1<<(m-1)) 就会在 $m=30, n=25$ 时变成计算 (1<<25) - (1<<29) = 33554432 - 536870912 = -503316480。 反事实实验：我们通过关闭 m > n 时的交换逻辑并输入 30 25 再次运行程序，结果果然输出了这个错误的负数，这充分证明了这个交换逻辑是绝对必要的承重代码。

2. 左移操作的数据类型陷阱 题面背景提到了有 64 格的 $2^{64}-1$，虽然该题数据只要求了 $n \le 30$，最大和 $2^{30}-1$ 在 32 位有符号整数内。 但按照统一的项目规范，对于这种呈指数增长的题目，我们始终采用 long long 避免可能的值域或者移位溢出问题。特别需要注意的是，在 C++ 里，左移的结果类型由左操作数的类型决定。 因此我们必须写成 1LL << n，用 64 位的字面量 1LL 来进行移位，而绝不能写成 1 << n。 另外，因为题目数据给的 $n \le 30 < 63$，移位是安全的，不会发生未定义行为（Undefined Behavior）。