2020牛客暑期多校训练营（第九场）A-Groundhog and 2-Power Representation

题目大意

输入计算式，求解。其中2(x)表示2的x次方，式中每一项都对应着答案在二进制表示下的数位为1的位。

解题思路

高精度快速幂，冲冲冲！
但是要注意的是具体实现时的细节（队友的高精度写的一堆Bug），还有读入时一层层递归下去。

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[1005],ans[205],t,l,lans;
long long sum;
char s[20010];
void big_multi(int a[],int len)
{
    lans=max(lans,len);
    for(int i=1;i<=lans;i++)
        ans[i]+=a[i],ans[i+1]+=ans[i]/10,ans[i]%=10;
    while(ans[lans+1]) lans++;
}
void big_qpow(long long x)
{
    int y=1,z,i,j;
    memset(a,0,sizeof(a));
    a[1]=1;
    for(i=1;i<=x;i++)
    {
        z=0;
        for(j=1;j<=y;j++)
        {
            a[j]=a[j]*2+z,z=a[j]/10,a[j]%=10;
            if(z && j==y) y++;
        }
    }
    big_multi(a,y);
}
long long qpow(long long x,long long y)
{
    long long z=1;
    while(y) 
    {
        if(y&1) z*=x;
        y>>=1,x*=x;
    }
    return z;
}
long long calc(long long x,long long y)
{
    long long z=0;
    t=0;
    for(int i=x;i<l;i++)
    {
        t=max(t,i);
        if(s[i]=='(') y++;
        if(s[i]==')') y--;
        if(!y)
        {
            big_qpow(z);
            return 0;
        }
        if(s[i]==')') return qpow(2,z);
        if(s[i]=='2')
        {
            if(s[i+1]=='(') z+=calc(i+1,y),i=t;
            else z+=2;
        }
    }
}
int main()
{
    int i;
    scanf("%s",s);
    l=strlen(s);
    for(i=0;i<l;i++)
        if(s[i]=='2')
        {
            if(s[i+1]!='(')
            {
                memset(a,0,sizeof(a));
                a[1]=2;
                big_multi(a,1);
            }
            else calc(i+1,0),i=t;
        }
    for(i=lans;i>=1;i--)
        printf("%d",ans[i]);
}