借鉴了 @println好好学习 在算法基础课《1.4数组》下的文章，在此表示感谢。

#include <iostream>

const int N = 10010;

using namespace std;


int main() {
    /*
    T: O() 外部循环为n次，也就是n的幂次，内部循环为数字的长度，也就是 n\log_{10}{2} ， 因此复杂度为 n * (n\log_{10}{2})
    S: O() 数字的长度  n\log_{10}{2}
    idea:
     构成要件：一个数组存储数字；一个全局变量记录进位【每次进位实质上就是将其向右移动一位】；一个局部变量。存储累乘，然后累加的数字；
     基本逻辑：近似于斐波那契数列的逻辑，每次乘以前面的数字，然后存储，这里累乘的是2，初始值是1；其中幂次n作为了外部循环
    */
    // 最低为数字是1，因为它乘以任何数都是任何数
    int a[N] = {1};
    int n;
    cin >> n;
    int m = 1;
    // 输入的 n 是 2 的幂次，并非乘数
    for (int i = 0; i < n; i++) {
        int t = 0;
        // 循环内的数字从低位不断被取出，这些数字都从左到右存放，也就是个位数在最左端，每次从数组a中读取个位十位，分别与 2 相乘
        // 运算后把数字存回原数组
        for (int j = 0; j < m; j++) {
            t += a[j] * 2;
            a[j] = t % 10;
            t /= 10;
        }
        // 负责进位，for循环最后一个操作是 t / 10，由于乘以2，最大为19， 因此若商为1，必定进位1
        if (t) a[m++] = 1;
        // 这里的m++，是在数组中自动给进位腾出一个位置，比如计算2^5，在n==4时a[0] = 16 --> a[0] = 6 --> t = 1 --> a[1] = 1; m == 2；
        //在n==5时就能对a[0], a[1]都进行运算：a[0] = 12 --> a[0] = 2 --> a[1] == 1 --> a[1] += 2，即a[1] == 3。
    }

    for (int i = m - 1; i >= 0; i--) cout << a[i];

    return 0;
}