题目大意
输入计算式,求解。其中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]); }