CTS2019 重复

题目大意: 给一个串s,求有多少个串t使得存在t....t的一个长度(|s|)的子串字典序小于s

首先转换成全部都大于等于s。

考虑在kmp自动机上跑t这个串，注意这个自动机的有些路是不能走的。

首先考虑当前已经有无数个t在前面，现在再加入一个t串，显然，如果起始节点是(u)，新加入的一个t走完与加入之前等价，即会走回(u).

冷静分析这个kmp自动机，发现每个节点的转移只有两种合法：一种是转移到0，另外一种是转移到nxt链上最大的匹配节点。

于是每次dp是(O(nm))的复杂度。并且(n)与(m)的大小关系无关。

于是现在我们有一个(O(n^2m))的部分分了

考虑到如果全部不走到0只有一种方案，所以对每个起点枚举第一次走到0的位置，dp可以(O(nm))预处理。

这样就做到(O(nm))了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
inline void upd(int &a,int b){a=add(a,b);}
/* math */
const int N = 2e3+5;
char s[N];
int n,m;
int nxt[N],maxpos[N];
int dp[N][N];

int main()
{
	cin >> m;scanf("%s",s+1);n=strlen(s+1);
	maxpos[0]=1;
	for(int i=1;i<=n;i++){
		int cur=nxt[i-1];
		while(cur&&s[cur+1]!=s[i])cur=nxt[cur];
		if(s[cur+1]==s[i]&&i!=1)++cur;
		nxt[i]=cur;maxpos[i]=maxpos[cur];
		if(s[i+1]>=s[maxpos[cur]])maxpos[i]=i+1;
	}
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			upd(dp[i][maxpos[j]],dp[i-1][j]);
			upd(dp[i][0],mul(dp[i-1][j],('z'-s[maxpos[j]])));
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++){
		int pos=i;
		for(int j=0;j<m;j++){
			if(pos==0){
				upd(ans,dp[m-j][i]);
				break;
			}
			upd(ans,mul(dp[m-j-1][i], 'z'-s[maxpos[pos]]));
			pos=maxpos[pos];
			if(j==m-1&&pos==i){
				upd(ans,1);
			}
		}
	}
	printf("%d
",sub(qpow(26,m),ans));
}