#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int> mul(vector<int> &a, vector<int> &b)
{
    int len = a.size() + b.size();
    vector<int> c(len, 0);
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < b.size(); j++)
        {
            c[i + j] += a[i] * b[j];
        }
    }
    for (int i = 0; i + 1 < c.size(); i++)
    {
        c[i + 1] += c[i] / 10;
        c[i] %= 10; 
    }
    while (c.size() > 1 && !c.back()) c.pop_back();
    while (c.size() > 500) c.pop_back();
    return c;
}
vector<int> ksm(vector<int> &a, ll b)
{
    vector<int> res(1, 1);
    while (b)
    {
        if (b & 1) res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}
void print(vector<int> &c)
{
    int len = n * log10(2) + 1; 
    cout << len << "\n";
    while (c.size() < 500) c.push_back(0);
    c[0] -= 1;
    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    vector<int> a(1, 2);
    a = ksm(a, n);
    print(a);
    return 0;
}

高精快速幂

这道题刚开始我也是不会啊，后来找了找大佬写的快速幂板子还有比较神奇的高精度算法，这才大明白。 这道题分为两部分：

1. 求位数。这个很好算只要把这个数和$10^n$联系起来就好了。方法是$ceil(p*lg2)$或者$(int)(p*lg2+1)$
2. 求后五百个数。直接模拟，把它算出来，但是p太大，需要快速幂。快速幂的代码和快速取模代码很想。原理就是二分指数。至于高精度，有个大佬用数组第0位表示数位，只计算前500位就行了。

while(p>0){
    if(p&1) a*=b;
    p >>= 1;
    b *= b;
}

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 20010
void mul(int a[],int b[]);
int p,A[N]={0},B[N]={0};
int main(){
	scanf("%d",&p);
	int l = ceil(p*log10(2));
	printf("%d\n",l);
	A[0] = 1; A[1] = 1;
	B[0] = 1; B[1] = 2;
	while(p>0){
		if(p&1) mul(A,B);
		p >>= 1;
		mul(B,B);
	}
	A[1] -= 1;
	for(int i=1,j=500;i<=500;i++){
		printf("%d",A[j--]);
		if(i%50 == 0) printf("\n");
	}
	return 0;
}
void mul(int a[],int b[]){
	int sum[N]={0};
	sum[0] = a[0]+b[0];
	if(sum[0]>500) sum[0] = 500;
	for(int i=0;i<a[0];i++){
		for(int j=0;j<b[0];j++){
			sum[i+j+1] = a[i+1]*b[j+1] + sum[i+j+1];
			if(sum[i+j+1]>=10){
				sum[i+j+2] += sum[i+j+1]/10;
				sum[i+j+1] %= 10;
			}
		}
	}
	for(int i=0;i<=sum[0];i++) a[i] = sum[i];
}