题目链接

https://www.dotcpp.com/oj/problem1607.html

题目大意

计算2^p-1位数，及低500位数，输出。

解题思路

2的p次方，快速幂吧！
只不过快速幂中的乘，得换成高精度乘法了。
先看看快速幂的板子吧
还不知道啥是快速幂看看这个吧

ll ksm(ll x,ll t){//快速幂
     ll res=1;
     while(t>0){
          if(t&1LL) res=res*x%mod;
         t>>=1;
          x=x*x%mod;
    }
     return res;
}

类比一下，乘换成高精度，把取模操作去掉。

我的AC代码

直接对着代码讲吧，方便理解。
先整体看看，不看细节。
先看主函数高精度快速幂求出2^p，所谓高精度快速幂不过是把单精度加减乘除换成高精度的；
res--，求出的res的最低位要-1，求出2^p-1；
ceil，天花板的意思，就是取大于某数的最小整数。相对的，floor，地板，取小于某数的最大整数。重点是这个数学公式（根本没听说过），ceil(幂*log10(底数)) = 底数^幂的位数；
输出。

函数讲解：
mul函数：高精度相乘，但是针对本题而言，因为我们只取低500位，因此，没必要用字符串存再转化，直接用数组存就行。这样一来，循环的终点都是500了，我们给全局数据res（即存最终答案的数组）赋值的时候，也是直接按着c的顺序赋值的，没必要反过来，反过来之后，再次进入相乘的时候，又要反过来计算，计算完了又反过来，可见，这是多此一举，所以，用res的低索引存低位。
x_mul函数：求x的平方，依然是只取低500位，与mul函数代码类似。

//我的代码 
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int res[N]={0,1},x[N]={0,2};//初始化不能忘！！忘掉爆炸！！
int c[N];

void mul(int* a,int* b){
    memset(c,0,sizeof c);//勿忘

    for(int i=1;i<=500;i++)//不管结果有多少位，我们只管最低500位，且低位的数值是不受高位影响的，但是高位的话会受到低位影响
        for(int j=1;j<=500;j++){//高精度乘法板子
            c[i+j-1]+=a[i]*b[j];
            c[i+j]+=c[i+j-1]/10;
            c[i+j-1]%=10;
        }

    for(int i=1;i<=500;i++)
        res[i]=c[i];//res与c数组相同的存储方式，小索引存低位    
}
void x_mul(){
    memset(c,0,sizeof c);//勿忘

    for(int i=1;i<=500;i++)
        for(int j=1;j<=500;j++){
            c[i+j-1]+=x[i]*x[j];
            c[i+j]+=c[i+j-1]/10;
            c[i+j-1]%=10;
        }

    for(int i=1;i<=500;i++)
        x[i]=c[i];
}
int main(){
    int p;
    cin>>p;
    int tmp=p;
        //快速幂变形而已
     while(tmp>0){
          if(tmp&1) mul(res,x);
         tmp>>=1;
          x_mul();
    }
    res[1]--;//求出的res的最低位要-1，因为要求2^p-1
    //为什么直接最低位-1就行，万一个位数是0呢？
        //其实，根本不存在个位为0的情况，至少也是2，因为2^1=2，无论乘多少个2，个位显然都不会变成0吧，除非乘0，所以你可以放心地进行-1；
    cout<<ceil(p*log10(2));//ceil函数+数学公式

    for(int i=500;i>=1;i--){//输出
        if((i)%50==0) cout<<endl;
        cout<<res[i];        
    }    
}

大佬的AC代码

本质没变，还是高精度快速幂。
大佬有三个函数，pow_2函数：高精度平方函数，mul_2函数：高精度乘2函数，get_res函数：快速幂函数。
get_res函数：
递归调用自己，若幂/2不为1，继续递归调用自己，参数为n/2；
进行平方操作；
若x为奇数，将结果进行乘2操作。
（不是很会讲，你可以举几个例子试试，你可以理解为一个木棒，不停地截取一半，要是能正好分一半，就平方，没法正好分一半，就平方后再乘上2）
pow_2函数：
类板子，求平方，取低500位。
mul_2函数：
类板子，*2操作，取低500位。

#include<bits/stdc++.h>
using namespace std;
const int N=1200;
int res[N];
int p;
void pow_2(){
    int c[N];
    memset(c,0,sizeof c);

    for(int i=1;i<=500;i++)    
        for(int j=1;j<=500;j++)
            c[i+j-1]+=res[i]*res[j];
    for(int i=1;i<=500;i++){
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }

    for(int i=1;i<=500;i++)
        res[i]=c[i];
}
void mul_2(){
    int c[N];
    memset(c,0,sizeof c);

    for(int i=1;i<=500;i++)
        res[i]*=2;
    for(int i=1;i<=500;i++){
        res[i+1]+=res[i]/10;
        res[i]%=10;
    }

}
void get_res(int x){
    if(x/2!=1) get_res(x/2);
    pow_2();
    if(x%2==1) mul_2();
}
int main(){
    cin>>p;
    cout<<ceil(p*log10(2));

    res[1]=2;
    get_res(p);
    res[1]--;

    for(int i=500;i>=1;i--){
        if(i%50==0) cout<<endl;
        cout<<res[i];
    }
}

二者区别

我的代码：
图片说明
大佬代码：

“正确”后的两个数依次是“内存”和“耗时”。

总结

尽管知道是高精度快速幂，但是还是没实现出来，最后还是仿照大佬的代码去实现了一遍。
重点记忆：
ceil(幂*log10(底数)) 为底数^幂的位数；
不同的快速幂板子。