「CTS2019 | CTSC2019」重复(Kmp)

Posted on Edited on In

「CTS2019 | CTSC2019」重复(Kmp)

Part1

首先我们考虑对于一个已经确定的 \(t\) 串，如何检查是否合法

对于 \(s\) 串建立 \(\text{kmp}\) ( \(\text{kmp}\) 自动机当然可以)，

如果当前 \(\text{kmp}\) 指针 \(j\) 在 \(\text{fail}\) 树上的祖先所对应的所有下一个位置 \(s[ancestor+1]\) 中，存在一个字符， \(t\) 中当前位置的字符 \(t[i]<s[ancestor+1]\)

那么就是存在一个"有意义的串",并且这个串和s串第一个不同的位置就是 \(ancestor+1\)

所以可以预处理一个 \(fail\) 树上祖先最大的 \(s[ancestor+1],Max[state]\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
rep(i,1,n) Max[i-1]=s[i];
Max[n]='a';//边界条件
cmax(Max[1],Max[0]);
rep(i,2,n) {
	int j=nxt[i-1];
	while(j && s[i]!=s[j+1]) j=nxt[j];
	if(s[i]==s[j+1]) ++j;
	nxt[i]=j;
	cmax(Max[i],Max[j]);
}
//预处理Max
rep(i,0,n) {
	if(i<n) Trans[i][s[i+1]-'a']=i+1;
	rep(j,0,25) if(j!=s[i+1]-'a') Trans[i][j]=Trans[nxt[i]][j];
}//kmp自动机，不要再暴力了
rep(i,m+1,n+m) t[i]=t[i-m]; // 延长到n+m就够了
int j=0,f=0;
rep(i,1,n+m){
	if(t[i]<Max[j]) { // 存在一个位置满足即可
		f=1;
		break;
	}
	j=Trans[j][t[i]-'a'];
}

配合dfs枚举，可以拿到pts10

Part2

设状态转移为 \(Trans[state][c]\)

把kmp状态压进dp状态里

如果把问题直接放到无穷意义下来看

那么跑够长度之后，后面的任意加入 \(m\) 次字符都会构成一个循环

枚举循环开始状态为 \(st\) ， \(\text{dp}\) 走了 \(m\) 步回到 \(st\) 的方案数

如果计算合法方案数，那么还要多一维，所以直接计算不合法方案，也就是

\(Trans[state][Max[state]..25]\) 这一段转移是不会出现合法情况的

最后减一下

复杂度 \(O(m\cdot n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace pt2{
	int dp[2][N];
	void Solve(){
		int cur=0,ans=0;
		rep(st,0,n) { // 枚举初始状态
			rep(i,0,n) dp[cur][i]=dp[!cur][i]=0;
			dp[cur][st]=1;
			rep(t,1,m) {
				cur^=1;
				rep(i,0,n) if(dp[!cur][i]){
					rep(c,Max[i]-'a',25) {//只转移不合法的
						dp[cur][Trans[i][c]]+=dp[!cur][i];
						Mod1(dp[cur][Trans[i][c]]);
					}
					dp[!cur][i]=0;
				}
			}// 走m步回到st
			ans+=dp[cur][st],Mod1(ans);
		}
		ans=(qpow(26,m)-ans+P)%P;//减一下
		printf("%d\n",ans);
	}
}


Part3

观察上面一档情况，合法的转移 \(Trans[state][Max[state]..25]\)

如果枚举下一个字符 \(c>Max[state]\) ，那么在 \(s\) 串中就找不到任何匹配了，下一个状态就是 \(0\)

否则，下一个状态就是 \(Trans[state][c]\)

也就是说，每个点出发其实只有两种情况，一种是一定会经过 \(0\) 的

所以对于这个环是否经过 \(0\) 进行讨论

如果不经过 \(0\) ，那么考虑直接从 \(st\) 出发走 \(m\) 步非0转移即可

经过 \(0\) 的，预处理一个从 \(0\) 出发，走了 \(i\) 步第一次回到 \(0\) 的方案数

\([st\rightarrow 0,0\rightarrow 0,0\rightarrow 0...,0\rightarrow st]\)

长成这个样子的转移

枚举第一个 \(st\rightarrow 0\) 的时间，后面可以预处理出来

复杂度 \(O(n\cdot m)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define reg register
typedef long long ll;
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

template <class T> void cmin(T &a, T b){ ((a>b)&&(a=b)); }
template <class T> void cmax(T &a, T b){ ((a<b)&&(a=b)); }


char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2010,P=998244353;

int n,m;
char s[N];
int Max[N],nxt[N],Trans[N][26];
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int st[N][N]; // 从i出发，走了j步第一次到0
int dp[N][N]; // 从0出发，走了i步，到了j,如果到0就不进行转移 

int main(){
	freopen("repeat.in","r",stdin),freopen("repeat.out","w",stdout);
	m=rd();
	scanf("%s",s+1),n=strlen(s+1);
	rep(i,1,n) Max[i-1]=s[i];
	Max[n]='a';
	cmax(Max[1],Max[0]);
	rep(i,2,n) {
		int j=nxt[i-1];
		while(j && s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) ++j;
		nxt[i]=j;
		cmax(Max[i],Max[j]);
	}
	rep(i,0,n) {
		if(i<n) Trans[i][s[i+1]-'a']=i+1;
		rep(j,0,25) if(j!=s[i+1]-'a') Trans[i][j]=Trans[nxt[i]][j];
	}

	int ans=0;	
	st[0][0]++;
	rep(i,1,n) {
		int j=i,f=1;
		rep(k,1,m) {
			st[i][k]+=25-(Max[j]-'a'),j=Trans[j][Max[j]-'a'];
			if(!j) {
				st[i][k]++,f=0;
				break;
			}
		}
		if(j==i) ans+=f;
	}

	dp[0][0]=1;
	rep(i,1,m) {
		rep(j,0,n) if(dp[i-1][j]) {
			dp[i][Trans[j][Max[j]-'a']]+=dp[i-1][j],Mod1(dp[i][Trans[j][Max[j]-'a']]);
			dp[i][0]=(dp[i][0]+1ll*(25-(Max[j]-'a'))*dp[i-1][j])%P;
		}
	}

	rep(i,0,n) { // 枚举初始状态
		rep(j,0,m) if(st[i][j] && dp[m-j][i]) { // 枚举走了几步第一次到0
			ans=(ans+1ll*st[i][j]*dp[m-j][i])%P;
		}
	}
	ans=(qpow(26,m)-ans+P)%P;
	printf("%d\n",ans);
}