G1030 [GESP202609 一级] 棋盘上的奖赏 题解

难度：1（GeekPi教学评定）；知识点：乘方、整数运算。

解题思路

第一格1粒，后面每格翻倍，总数是1+2+…+2^(n-1)=2^n-1。也可维护当前格数量，每次加到总数后乘2。参考代码用1LL<<n计算2^n。

为什么正确

设总和S=1+2+…+2^(n-1)，则2S-S=2^n-1，得到所用公式；逐格累加也能直接验证。

易错点

n个格子的末项是2^(n-1)；使用long long，且位移的左操作数是1LL。本题n≤30。

复杂度

时间：O(1)；逐格累计写法为O(n)；额外空间：O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    cout<<((1LL<<n)-1);
}

来源与说明

本题解为配套教学整理，非官方题解。题库使用自行生成的测试数据，5个测试点。