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

Groundhog and 2-Power Representation

原题请看这里

题目描述：

土拨鼠参加了数学课。 在这堂课上，他的数学老师说：
任何正整数都可以用 ${2}$的幂表示。
例如： $137 = 2 ^ 7 + 2 ^ 3 + 2 ^ 0$。
幂用括号表示。即， ${a(b)}$代表 ${a ^ b}$。因此， ${137}$可以表示为 $137 = {2(7)+2(3)+2(0) }$
此外，对于 $7 = 2 ^ 2 + 2 + 2 ^ 0$( $2 ^ 1$用 ${2}$表示）， $3 = 2 + 2 ^ 0$
，137可以最终表示为 ${137 = 2(2(2)+ 2 + 2(0))+ 2(2 + 2(0))+ 2(0)}$
另一个示例： $1315 = 2 ^ {10} + 2 ^ 8 + 2 ^ 5 + 2 + 1 = 2(2(2 + 2(0))+ 2)+2(2(2 + 2(0))) +2(2(2)+2(0))+ 2 + 2(0)$
土拨鼠感觉很棒，希望您编写一个模拟上述内容的程序。您需要读入 ${2}$的幂的表达式并计算其值。

输入描述：

一行，表示一个2的幂的表达式。

输出描述：

输出表达式的值。

样例输入：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

样例输出：

1315

思路：

$AC$ $Code$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
char a[20010];
ll sum;
int ans[205],anslen;
void gaojin(int b[],int len){anslen=max(anslen,len);for(int i=1;i<=anslen;++i){ans[i]+=b[i];ans[i+1]+=ans[i]/10;ans[i]%=10;}while(ans[anslen+1]) ++anslen;
}
int b[1005];
void ksm(ll c){memset(b,0,sizeof(b));b[1]=1;int k=1;for(int i=1;i<=c;++i){int x=0;for(int j=1;j<=k;++j){b[j]=b[j]*2+x;x=b[j]/10;b[j]%=10;if(x&&j==k) ++k;}}gaojin(b,k);
}
ll ksm1(ll b,ll c) {ll d=1;while(c>0) {if(c&1)d*=b;c>>=1;b*=b;}return d;
}
int p,k;
ll dg(ll x,ll h){ll q=0;p=0;for(int i=x;i<k;i++){p=max(p,i);if(a[i]=='(')h++;if(a[i]==')')h--;if(!h){ksm(q);return 0;}if(a[i]==')'){return ksm1(2,q);}if(a[i]=='2'){if(a[i+1]=='(') q+=dg(i+1,h),i=p;else q+=2;}}
}
int main(){scanf("%s",a);k=strlen(a);for(int i=0;i<k;i++)if(a[i]=='2'){if(a[i+1]!='('){memset(b,0,sizeof(b));b[1]=2;gaojin(b,1);}else dg(i+1,0),i=p;}for(int i=anslen;i>=1;i--)printf("%d",ans[i]);
}