对于题中的"normal expression"（仅含加减乘和无前导0的非负整数，无括号）的计算，实际上并不需要通常的表达式求值，而可以用下述方式计算——
维护三元组$(a,b,c)$，分别表示已经确定的部分、下一个$pm$之前这些数的系数和当前最后一个数字（或许解释并不清晰，可以参考转移），三者初始为$(0,1,0)$，并不断加入下一个字符$d$，转移如下
$$
egin{cases}a'=a+bc,b'=1,c'=0&(+)\a'=a+bc,b'=-1,c'=0&(-)\a'=a,b'=bc,c'=0&(*)\a'=a,b'=b,c'=10c+d&(num)end{cases}
$$
再额外维护一个$bc$后，转移即均为线性，那么可以用矩阵描述
（具体实现还要再维护一个1，因此矩阵大小为$5 imes 5$）
另外，若最终得到的三元组为$(a,b,c)$，则答案即为$a+bc$
最终，总复杂度为$o(5^{3}tl)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 300005 4 #define mod 1000000007 5 #define ll long long 6 int t,n,flag; 7 ll m; 8 char s[N]; 9 struct matrix{ 10 int a[5][5]; 11 matrix(int p=0){ 12 memset(a,0,sizeof(a)); 13 for(int i=0;i<5;i++)a[i][i]=p; 14 } 15 }o,ans,A[13]; 16 int change(char c){ 17 if (c=='+')return 10; 18 if (c=='-')return 11; 19 if (c=='*')return 12; 20 return c-'0'; 21 } 22 matrix mul(matrix a,matrix b){ 23 matrix ans; 24 for(int i=0;i<5;i++) 25 for(int j=0;j<5;j++) 26 for(int k=0;k<5;k++)ans.a[i][j]=(ans.a[i][j]+(ll)a.a[i][k]*b.a[k][j])%mod; 27 return ans; 28 } 29 matrix qpow(matrix a,ll m){ 30 matrix s=a,ans(1); 31 while (m){ 32 if (m&1)ans=mul(ans,s); 33 s=mul(s,s); 34 m>>=1; 35 } 36 return ans; 37 } 38 int main(){ 39 for(int i=0;i<10;i++){ 40 A[i].a[0][0]=A[i].a[1][1]=A[i].a[2][2]=1; 41 A[i].a[0][3]=A[i].a[2][4]=i; 42 A[i].a[3][3]=A[i].a[4][4]=10; 43 } 44 A[10].a[0][0]=A[10].a[1][1]=A[10].a[4][1]=A[10].a[0][2]=1; 45 A[11]=A[10],A[11].a[0][2]=mod-1; 46 A[12].a[0][0]=A[12].a[1][1]=A[12].a[4][2]=1; 47 scanf("%d",&t); 48 while (t--){ 49 scanf("%s",s); 50 n=strlen(s),flag=0,ans=matrix(1); 51 for(int i=0;i<n;i++){ 52 if (flag){ 53 if (s[i]=='('){ 54 m=0; 55 continue; 56 } 57 if (s[i]!=')')m=m*10+s[i]-'0'; 58 else{ 59 ans=mul(o,qpow(ans,m)); 60 flag=0; 61 } 62 continue; 63 } 64 if (s[i]=='('){ 65 o=ans,ans=matrix(1); 66 continue; 67 } 68 if (s[i]==')')continue; 69 if (s[i]=='#')flag=1; 70 else ans=mul(ans,A[change(s[i])]); 71 } 72 printf("%d ",((ans.a[0][1]+ans.a[2][1])%mod+(ans.a[0][4]+ans.a[2][4])%mod)%mod); 73 } 74 return 0; 75 }