Kuangbin_KMP_O题(LightOJ-1268)

发表于 |

【题面描述】
求由字典集T（仅包含小写字母）生成的长度为m，且不包含子串S（|S|≤50）的字符串总数量，对$2^{32}$取模。m不超过${10}^9$。

神烦的dp套KMP= =看数据规模容易以为是CTA算法题(Contribute To the Answer)，但居然是矩阵快速幂优化dp= =感觉没见过的话很不可做，但据说已经是经典老题了，还有AC自动机版本……

取模就是两眼一闭，自然溢出。

首先得迅速解决n比较小时的问题，否则就会想偏。
f[i][j]表示第i位文本串匹配到第j位模式串的合法方案数，其中规定j尽可能大。初值为f[0][0]=1，转移时对每个模式串的位置j枚举下一个字母k，遍历j的next祖先，找到能成功匹配到k的最大位置，这就是应当转移到的目标；如果匹配完成，那么不计入答案。显然这一步与i无关，所以可以预处理mtx数组，其中mtx[j][k]表示第j位模式串后接上k应当转移到的位置，对每个j和k暴力跑next即可。这样在跑dp时，对每一对(j,k)，可以$O(1)$地找到要转移到的位置，将方案数累加即可（刷表法）。答案就是$\displaystyle\sum_{i=0}^{|S|-1}f[m][i]$。dp时间复杂度为$O(m|S||T|)$，预处理时间复杂度为$O(|S|^2|T|)$。其实可以通过进一步预处理，使预处理时不用枚举k，复杂度下降为$O(|S|^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
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
/*
 *powered by caibiCH2
 *create at 2019-09-18 23:09:46
 */
#include <bits/stdc++.h>
#define elif else if
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) (xiangdangyu(y)?(x):(y))
#define INF 0x3f3fxiangdangyu
typedef long long ll;

using namespace std;

vector<int>getNext(const string&s){
	int j=0,k=-1,l=s.length();
	vector<int>next(l+1);
	next[0]=-1;
	while(j<l){
		if(k==-1||s[j]==s[k])
			next[++j]=++k;
		else k=next[k];
	}
//	for(auto i:next)cout<<i<<' ';
	return next;
}

unsigned f[101000][60];
unsigned mtx[60][60];
int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int T;cin>>T;
	for(int o=1;o<=T;o+=1){
		int m;cin>>m;
		string s1,s2;cin>>s1>>s2;int n=s2.length();
		auto next=getNext(s2);
		memset(mtx,0,sizeof(mtx));
		for(int j=0;j<n;j+=1){
			for(int k=0;k<s1.length();k+=1){
				for(int t=j;;t=next[t]){
					if(t==-1||s1[k]==s2[t]){mtx[j][k]=t+1;break;}
				}
			}
		}
		f[0][0]=1;
		for(int i=1;i<=m;i+=1){
			for(int j=0;j<n;j+=1){
				f[i][j]=0;
			}
			for(int j=0;j<n;j+=1){
				for(int k=0;k<s1.length();k+=1){
					f[i][mtx[j][k]]+=f[i-1][j];
				}
			}
		}
		ll ans=0;
		for(int i=0;i<n;i+=1){
			ans+=f[m][i];
		}
		cout<<ans<<endl;
	}
	return 0;
}

然后可以发现，$f[i][j]$只由$f[i-1][j]$转移而来。所以可以用填表法表示转移方程：

莫名其妙多了一维？但可以发现，对于每对(p,j)，我们只关心有多少个k，使得mtx[p][k]==j，也就是说可以再次预处理m0[p][j]表示满足条件的k的数量。
于是修改转移方程（顺便重新命名了一些字母）:

初值还是f[0][0]=1。
我们发现了什么？如果把f[i]写成行向量，那么这就是矩阵乘法的形式！那么就变成矩阵快速幂的板子了。
但本人习惯写方阵×列向量的形式，所以dp方程（强行）改为：

由于初值只有f[0][0]=1，所以乘完后答案就是第0列的和，不必再进行一次矩阵乘法了。

另外，两步预处理可以合成一步，还是省略k的信息，比较容易就不再赘述了。

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
/*
 *powered by caibiCH2
 *create at 2019-09-18 23:09:46
 */
#include <bits/stdc++.h>
#define elif else if
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;

vector<int>getNext(const string&s){
	int j=0,k=-1,l=s.length();
	vector<int>next(l+1);
	next[0]=-1;
	while(j<l){
		if(k==-1||s[j]==s[k])
			next[++j]=++k;
		else k=next[k];
	}
//	for(auto i:next)cout<<i<<' ';
	return next;
}

unsigned mtx[60][60];
struct matrix{
	unsigned data[60][60],n;
	void init(int u){
		n=u;
		for(int i=0;i<=n;i+=1){
			for(int j=0;j<=n;j+=1){
				data[i][j]=0;
			}
		}
	}
	friend matrix operator*(const matrix&a,const matrix&b){
		matrix c;c.init(a.n);
		for(int i=0;i<c.n;i+=1){
			for(int j=0;j<c.n;j+=1){
				for(int k=0;k<c.n;k+=1){
					c.data[i][j]+=a.data[i][k]*b.data[k][j];
				}
			}
		}
		return c;
	}
}m0;
matrix qpow(matrix x,long long y){
	matrix t;
	t.init(x.n);
	for(int i=0;i<x.n;i+=1){
		t.data[i][i]=1;
	}
	while(y){
		if(y&1){t=t*x;}
		x=x*x;
		y>>=1;
	}
	return t;
}
int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int T;cin>>T;
	for(int o=1;o<=T;o+=1){
		int m;cin>>m;
		string s1,s2;cin>>s1>>s2;int n=s2.length();
		auto next=getNext(s2);
		memset(mtx,0,sizeof(mtx));m0.init(n);
		for(int j=0;j<n;j+=1){
			for(int k=0;k<s1.length();k+=1){
				for(int t=j;;t=next[t]){
					if(t==-1||s1[k]==s2[t]){++m0.data[t+1][j];break;}
				}
			}
		}
		
		m0=qpow(m0,m);
		unsigned ans=0;
		for(int i=0;i<n;i+=1){
			ans+=m0.data[i][0];
		}
		cout<<"Case "<<o<<": "<<ans<<'\n';
	}
	return 0;
}