题目描述
分析
从题目的备注
中可以看出
这道题的答案要用高精度计算和存储
于是模板先打好
struct BigInt
{ll a[B];BigInt(){}BigInt(ll x){a[0]=x;for(int i=0;i<B-1;i++){a[i+1]=a[i]/M;a[i]%=M;}}
};
BigInt add(BigInt x,BigInt y)
{BigInt ret;for(int i=0;i<B;i++)ret.a[i]=x.a[i]+y.a[i];for(int i=0;i<B-1;i++){ret.a[i+1]+=ret.a[i]/M;ret.a[i]%=M;}return ret;
}
BigInt mul(BigInt x,BigInt y)
{BigInt ret;memset(ret.a,0,sizeof(ret.a));for(int i=0;i<B;i++)for(int j=0;i+j<B;j++)ret.a[i+j]+=x.a[i]*y.a[j];for(int i=0;i<B-1;i++){ret.a[i+1]+=ret.a[i]/M;ret.a[i]%=M;}return ret;
}
void print(BigInt x)
{int f=-1;for(int i=B-1;~i;i--)if(x.a[i]){f=i;break;}if(f>=1){if(x.a[f]>0){for(int i=f;i;i--)x.a[i]--,x.a[i-1]+=M;}else{for(int i=f;i;i--)x.a[i]++,x.a[i-1]-=M;}for(int i=0;i<B-1;i++)x.a[i+1]+=x.a[i]/M,x.a[i]%=M;if(!x.a[f]) f--;printf("%lld",x.a[f]);for(int i=f-1;~i;i--)printf("%04lld",abs(x.a[i]));}else printf("%lld",x.a[0]);
}
然后因为题目中有二的幂，所以要再打一个高精度版本的快速幂
BigInt ksm_last_order(int b){BigInt a=BigInt(2);BigInt ret=BigInt(1);while(b){if(b&1) ret=mul(ret,a);a=mul(a,a),b>>=1;}return ret;
}
接下来分析一下给定的输入
发现符号^
被括号给代替了
所以要打括号匹配，并进行递归
int sol(int l,int r)
{int p=0;for(int i=l;i<=r;i++){if(s[i]=='(') p+=ksm(sol(i+1,mat[i]-1)),i=mat[i]+1;if(s[i]=='2') p+=2;}return p;
}
括号匹配
for(int i=1;i<=len;i++){if(s[i]=='(') st.push(i);if(s[i]==')'){int tp=st.top();st.pop();mat[tp]=i;if(tp==pre)ans=add(ans,ksm_last_order(sol(tp+1,i-1))),pre=i+2,ed=i;//因为调试时最后的2^1和2^0没加，所以用ed标记}}
然后输出就AC了
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int B=200,M=10000;
struct BigInt
{ll a[B];BigInt(){}BigInt(ll x){a[0]=x;for(int i=0;i<B-1;i++){a[i+1]=a[i]/M;a[i]%=M;}}
};
BigInt add(BigInt x,BigInt y)
{BigInt ret;for(int i=0;i<B;i++)ret.a[i]=x.a[i]+y.a[i];for(int i=0;i<B-1;i++){ret.a[i+1]+=ret.a[i]/M;ret.a[i]%=M;}return ret;
}
BigInt mul(BigInt x,BigInt y)
{BigInt ret;memset(ret.a,0,sizeof(ret.a));for(int i=0;i<B;i++)for(int j=0;i+j<B;j++)ret.a[i+j]+=x.a[i]*y.a[j];for(int i=0;i<B-1;i++){ret.a[i+1]+=ret.a[i]/M;ret.a[i]%=M;}return ret;
}
void print(BigInt x)
{int f=-1;for(int i=B-1;~i;i--)if(x.a[i]){f=i;break;}if(f>=1){if(x.a[f]>0){for(int i=f;i;i--)x.a[i]--,x.a[i-1]+=M;}else{for(int i=f;i;i--)x.a[i]++,x.a[i-1]-=M;}for(int i=0;i<B-1;i++)x.a[i+1]+=x.a[i]/M,x.a[i]%=M;if(!x.a[f]) f--;printf("%lld",x.a[f]);for(int i=f-1;~i;i--)printf("%04lld",abs(x.a[i]));}else printf("%lld",x.a[0]);
}
const int N=20010;
char s[N],ss[N];
int mat[N];
stack<int> st;
BigInt ans=BigInt(0);
BigInt ksm_last_order(int b){BigInt a=BigInt(2);BigInt ret=BigInt(1);while(b){if(b&1) ret=mul(ret,a);a=mul(a,a),b>>=1;}return ret;
}
int ksm(int b){if(!b) return 1;int a=2,ret=1;while(b){if(b&1) ret*=a;a*=a,b>>=1;}return ret;
}
int sol(int l,int r){int p=0;for(int i=l;i<=r;i++){if(s[i]=='(') p+=ksm(sol(i+1,mat[i]-1)),i=mat[i]+1;if(s[i]=='2') p+=2;}return p;
}
int main(){scanf("%s",ss+1);int lens=strlen(ss+1),len=0;for(int i=1;i<=lens;i++) if(ss[i]=='2'&&ss[i+1]=='(') ss[i]='?';for(int i=1;i<=lens;i++) if(ss[i]!='?') s[++len]=ss[i];int p=0,pre=1,ed;for(int i=1,val;i<=len;i++){if(s[i]=='(') st.push(i);if(s[i]==')'){int tp=st.top();st.pop();mat[tp]=i;if(tp==pre)ans=add(ans,ksm_last_order(val=sol(tp+1,i-1))),pre=i+2,ed=i;}}ans=add(ans,sol(ed+1,len));print(ans),putchar(10);
}