1 条题解
-
2
#include<bits/stdc++.h> using namespace std; typedef long long LL; char buf[1<<18],*p1=buf,*p2=buf; #define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++) int read() { int x=0; char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar(); return x; } void write(int x) { if(x>9) write(x/10); putchar(x%10+'0'); } const int MOD=998244353; inline int Add(int x,int y){return x+y>=MOD?x+y-MOD:x+y;} inline int Sub(int x,int y){return x<y?x-y+MOD:x-y;} inline int Mul(int x,int y){return 1ll*x*y%MOD;} int QuickPow(int x,int p) { int ans=1,base=x; while(p) { if(p&1) ans=Mul(ans,base); base=Mul(base,base); p>>=1; } return ans; } int n,m,k; int s[100005],nxt[100005]; struct BorderSeq{ int l,r,d; BorderSeq(){} BorderSeq(int L,int R,int D){l=L,r=R,d=D;} }brd[200005]; int cnt,dp[200005],sum[200005]; int pw[200005],ipw[200005]; void Kmp() { int j=0; for(int i=2;i<=k;++i) { while(j && s[j+1]!=s[i]) j=nxt[j]; if(s[j+1]==s[i]) ++j; nxt[i]=j; } int now=nxt[k],d=k-nxt[k],fir=nxt[k]; while(now) { if(d!=now-nxt[now] || !nxt[now]) brd[++cnt]=BorderSeq(now,fir,d),fir=nxt[now]; if(!nxt[now]) break; d=now-nxt[now],now=nxt[now]; } } vector<int> Sum[20][200005]; int pos[20][200005]; int main(){ n=read(),m=read(),k=read(); for(int i=1;i<=k;++i) s[i]=read(); Kmp(); int invm=QuickPow(m,MOD-2); pw[0]=ipw[0]=1; for(int i=1;i<=n;++i) pw[i]=Mul(pw[i-1],m); for(int i=1;i<=n;++i) ipw[i]=Mul(ipw[i-1],invm); memset(pos,-1,sizeof pos); for(int i=k;i<=n;++i) { dp[i]=Sub(pw[i-k],sum[i-k]); for(int j=1;j<=cnt;++j) { int d=brd[j].d,l=brd[j].l,r=brd[j].r; int idx=(l+i-k)%d; if(!Sum[j][idx].empty()) { int L=l+i-k,R=r+i-k; if(~pos[j][R]) dp[i]=Sub(dp[i],Sum[j][idx][pos[j][R]]); if(pos[j][L]>0) dp[i]=Add(dp[i],Sum[j][idx][pos[j][L]-1]); } } for(int j=1;j<=cnt;++j) { int d=brd[j].d; int idx=i%d; pos[j][i]=int(Sum[j][idx].size()); Sum[j][idx].push_back(Add(Sum[j][idx].empty()?0:Sum[j][idx].back(),dp[i])); } sum[i]=Add(Mul(sum[i-1],m),dp[i]); } int ans=0; for(int i=k;i<=n;++i) ans=Add(ans,Mul(dp[i],pw[n-i])); write(Mul(ans,ipw[n])); return 0; }
- 1
信息
- ID
- 393
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 12
- 已通过
- 9
- 上传者