解题思路

题目要求计算 2 + 2×2 + 2×2×2 + …… 共 n 项的和，也就是 2¹ + 2² + 2³ + … + 2ⁿ。n 最大 100，2^100 已经超过 int 的范围，所以要高精度。

思路分两步：

第一步：算出每一项 2¹、2²、……、2ⁿ

用二维数组 a[i] 存 2 的 i 次方，每一位数字存一格：

• a[0] = 1（2^0）
• 2^i = 2^(i-1) × 2，所以 a[i][j] = a[i-1][j] × 2，再处理进位

第二步：把所有项加起来

用一个数组 r 存总和，逐项把 a[1] 到 a[n] 累加进去，同样处理进位。

最后从最高位到个位逆序输出 r 就是答案。

为什么用数组存？ 因为数字太大（最多 31 位），int 装不下，用数组一位一位存，乘 2 和进位就都能处理了。

参考代码

#include <iostream>
using namespace std;

int main() {
    int a[100][100] = {0};
    int r[100] = {0};
    int n, k = 1;
    cin >> n;

    a[0][0] = 1;  // 2^0 = 1

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) a[i][j] = a[i - 1][j] * 2;
        for (int j = 0; j < k; j++) {
            if (a[i][j] >= 10) {
                a[i][j + 1] += a[i][j] / 10;
                a[i][j] = a[i][j] % 10;
            }
        }
        if (a[i][k] > 0) k++;
    }

    // 累加所有项
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            r[j] += a[i][j];
            if (r[j] >= 10) {
                r[j + 1] += r[j] / 10;
                r[j] = r[j] % 10;
            }
        }
        if (r[k] > 0) k++;
    }

    int p = 0;
    for (int i = k - 1; i >= 0; i--) {
        if (r[i] != 0) { p = i; break; }
    }
    for (int i = p; i >= 0; i--) cout << r[i];
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，n 项每项处理若干位
• 空间复杂度：O(N²)，二维数组存所有项