题目描述

Statement

Solution

有序列自动机思想如图思路就是用$res$处理循环的整个字符串，余数为$rem$ #include <bits/stdc++.h> using namespace std; const int N=1e6+10,A=27,mod=998244353; char sc[N]; int M1(int x){return x>=mod?x-mod:x;} int M2(int x){return x<0?x+mod:x;} int n,m,T,s[A][N],i,j,l,r,v,x,rem,ans,res,nxt,cur; int main() { scanf("%s",sc+1); n=strlen(sc+1); for(i=1;i<=n;i++) { for(j=0;j<A;j++) s[j][i]=s[j][i-1]; ++s[sc[i]-'a'+1][i]; ++s[0][i];//* }//sequence automata scanf("%d",&T); while(T--) { bool flag=0; scanf("%s",sc+1); m=strlen(sc+1); cur=1,ans=0; for(i=1;i<=m;i=r+1) { v=(sc[i]=='*')?0:sc[i]-'a'+1; x=s[v][n];//一次循环所有v个数 if(!x){flag=1;break;}//不存在(未出现v) r=i,res=0,rem=1;//数字右边界,商,余数 if(i+1<=m&&sc[i+1]>='0'&&sc[i+1]<='9') { l=i+1,rem=0;//数字左边界 while(r+1<=m&&sc[r+1]>='0'&&sc[r+1]<='9') ++r; for(i=l;i<=r;i++) rem=10*rem+(sc[i]-'0'), res=(10ll*res+(rem/x))%mod, rem%=x;//高精除低精 res=1ll*res*n%mod; if(!rem) rem=x,res=M2(res-n); } if(s[v][n]-s[v][cur-1]<rem) res=M1(res+n-cur+1),rem-=s[v][n]-s[v][cur-1],cur=1; nxt=lower_bound(s[v]+cur,s[v]+n+1,s[v][cur-1]+rem)-s[v]+1; res=M1(res+nxt-cur); cur=nxt,ans=M1(ans+res); } if(flag) puts("-1"); else printf("%d\n",ans); } }