YZOJ P3629 [校内训练20180406]表达式
时间限制：1000MS 内存限制：131072KB
出题人：zzx 难度：\(6.5\)
-
题目描述
本题中，我们需要计算一些“Bomb表达式”的结果。比如， “1-2+3” 的结果为 2 。和普通表达式不同的是，Bomb表达式中可能包含一些 “#” 号，会展开一些普通表达式。比如 “(1-2+3)#(3)” 表示 “1-2+3 ”出现了 3 次，将会被展开为 “1-2+31-2+31-2+3”，其结果为 60 。
为了方便理解，下面给出了Bomb表达式（bomb expression）和普通表达式（normal expression）的BNF表示。
|
1 2 3 4 5 6 7 8 9 |
<bomb expression> := <bomb term> | <bomb expression> <bomb term> <bomb term> := <bomb statement> | '(' <bomb statement> ')' '#' '(' <number> ')' <bomb statement> := <bomb element> | <bomb statement> <bomb element> <bomb element> := <digit> | '+' | '-' | '*' <normal expression> := <norm term> | <normal expression> '+' <norm term> | <normal expression> '-' <norm term> <norm term> := <number> | <norm term> '*' <number> <number> := <digit> | <non-zero-digit> <number> <digit> := '0' | <non-zero-digit> <non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' |
请先将Bomb表达式中所有的 # 号展开，使其成为普通表达式（题目的输入保证展开后是一个合法的普通表达式），然后计算这个表达式的结果。
-
输入格式
第一行一个正整数 \(T\)，表示输入数据组数。
接下来 \(T\) 行，每行一个字符串，为待计算的Bomb表达式。
-
输出格式
对于每组数据输出一行一个整数，表示表达式的结果，答案对 \(1,000,000,007\) 取模。
-
样例输入
|
1 2 3 4 5 6 7 8 |
7 1-2+3 (1-2+3)#(3) (1+2-3)#(3) (1)#(3) (1+)#(2)1 (2*3+1)#(2) (2)#(2)1+1(2)#(2) |
-
样例输出
|
1 2 3 4 5 6 7 |
2 60 999999949 111 3 43 343 |
-
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq T \leq 50\)，输入表达式的总长度不超过 \(300,000\)，<bomb term> 中的 <number> 不超过 \(10^{18}\) 。
神仙题目
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <cstdarg> #define MOD 1000000007 struct _vec { int a[4]; _vec(int ta=0,int tb=0,int tc=0,int td=0){a[0]=ta,a[1]=tb,a[2]=tc,a[3]=td;} }; struct _mat { int a[4][4]; _mat(){memset(a,0,sizeof(a));} inline void fill(int cnt,...) { va_list ap; va_start(ap,cnt); for(register int i=0;i<4 && cnt;i++) for(register int j=0;j<4 && cnt;j++,cnt--) a[i][j]=va_arg(ap,int); va_end(ap); } _mat operator * (const _mat&o)const { _mat ans; for(register int i=0;i<4;i++) for(register int j=0;j<4;j++) for(register int k=0;k<4;k++) (ans.a[i][j]+=(long long)this->a[i][k]*o.a[k][j]%MOD)%=MOD; return ans; } _vec operator * (const _vec&o)const { _vec ans; for(register int i=0;i<4;i++) for(register int j=0;j<4;j++) (ans.a[i]+=(long long)this->a[i][j]*o.a[j]%MOD)%=MOD; return ans; } }I,MD,MA,MM,MT,ML; inline _mat GetNumMat(register int x) { _mat c=MD; c.a[2][1]=x; return c; } template<class T> inline bool MatchAns(T&ans,register char c) { if(c=='+') ans=MA*ans; else if(c=='-') ans=MM*ans; else if(c=='*') ans=MT*ans; else if(c>='0' && c<='9') ans=GetNumMat(c-'0')*ans; else return false; return true; } inline _mat _pow(_mat base,long long b) { _mat ans=I; while(b) { if(b&1) ans=ans*base; base=base*base; b>>=1; } return ans; } char s[305050]; int main() { I.fill(16, 1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1); MD.fill(16, 1,0,0,0, 0,1,0,0, 0,0xFF,10,0, 0,0,0,1); MA.fill(16, 1,0,1,0, 0,0,0,1, 0,0,0,0, 0,0,0,1); MM.fill(16, 1,0,1,0, 0,0,0,-1, 0,0,0,0, 0,0,0,1); MT.fill(16, 1,0,0,0, 0,0,1,0, 0,0,0,0, 0,0,0,1); int T;scanf("%d",&T); for(register int lp=1;lp<=T;lp++) { _vec ans(0,1,0,1); scanf("%s",&s[1]); register int ls=strlen(&s[1]); for(register int i=1;i<=ls;i++) if(!MatchAns(ans,s[i])) { i++; _mat now=I; for(;i<=ls;i++) if(!MatchAns(now,s[i])) break; long long cnt=0; for(i+=3;s[i]!=')' && i<=ls;i++) cnt=cnt*10+s[i]-'0'; ans=_pow(now,cnt)*ans; } ans=MA*ans; printf("%d\n",(ans.a[0]+MOD)%MOD); } return 0; } |