Mivik

不会做

观摩题解后的感触

求概率取余时候除以的分母可以用模逆元转换为乘。

image-20251020201500960

还有就是KMP中的next数组可以转换为n个等差数列（顺序排列，不交叉）。也就是字符串边界理论（Border Theory）

题解里面FjswYuzu写的还可以,有时间学学。

题解(ctrl+c/v)

#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;
}