[HNOI2008]GT考试

题目描述

阿申准备报名参加 GT 考试，准考证号为 (N) 位数(X_{1},X_{2}…X_{n}(0≤X_{i}≤9))，他不希望准考证号上出现不吉利的数字。他的不吉利数学(A_{1},A_{2}…A_{m}(0≤A_{i}≤9）) 有 (M) 位，不出现是指 (X_{1},X_{2}…X_{n}) 中没有恰好一段等于 (A_{1},A_{2}…A_{m})，(A_{1}) 和(X_{1}) 可以为 (0)

输入格式

第一行输入(N),(M),(K).接下来一行输入M位的数。

输出格式

阿申想知道不出现不吉利数字的号码有多少种，输出模 (K) 取余的结果。

输入输出样例

输入 #1

4 3 100
111

输出 #1

说明/提示

(N≤10^{9},M≤20,K≤1000)

思路分析

本来就是想好好想练一下(KMP)，根据某谷标签找到了这道题，看题面那么简短，以为并不是很难（虽然是紫的），结果做着做着就傻了
这题很综合，(DP)+矩阵快速幂+(KMP)，我原地螺旋升天sto orz

状态转移：

设(dp[i][j])表示长度为(i)的字符串，最后(j)个可以匹配模式串前(j)位的情况数，答案就是(sum_{i=0}^{m-1}dp[n][i])
However,理论是有了，如何实现？
关键在于对模式串的不同匹配情况，用一个(g[k][j])对于一个匹配到长度为 (j)的串，转移到 (k) 的串的方案
此时转移方程(dp[i][j] = sum_{k=0}^{m-1}dp[i-1][k]*g[k][j])，你看，你看，你仔细看，这个式子像什么？矩阵乘啊！（本蒟蒻永远推不出来系列）
因为我们最后只需要(n)这一行矩阵，所以我们把每一行(dp[i][j])抽象成只有一行，列数为(m-1)的(F[i]),最后就变成了(F[i] = F[i-1]*G),推出(F[n] = F[0]*G^{n}),这时候就可以跑矩阵快速幂了

~~等会儿，我不是来练(KMP)的吗？？？~~

Code

#include<bits/stdc++.h>
#define N 25
using namespace std;
inline int read(){
	int x = 0,f =  1;
	char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,mod,kmp[N];
char s[N];
struct xzy{//定义矩阵
	int a[N][N];
	xzy(){memset(a,0,sizeof(a));}
}G,F;
xzy operator *(xzy a,xzy b){//矩阵乘法
	xzy ans;
	for(int i = 0;i < m;i++){
		for(int j = 0;j < m;j++){
			for(int k = 0;k < m;k++){
				ans.a[i][j] = (ans.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
			}
		}
	}
	return ans;
}
xzy quickpow(xzy g,int t){//矩阵快速幂
	xzy ans;
	for(int i = 0;i < m;i++)ans.a[i][i] = 1;
	while(t){
		if(t&1)ans = ans*g;
		g = g*g;
		t >>= 1;
	}
	return ans;
}
int main(){
	n=read();m=read();mod=read();
	scanf("%s",s+1);
	int j=0;
	for(int i=2;i<=m;++i) {//kmp求匹配情况
		while(j && s[j+1]!=s[i]) j=kmp[j];
		if(s[j+1]==s[i]) j++;
		kmp[i]=j;
	}
	
	for(int i=0;i<m;++i) {//算出所有未完全匹配的个数（这好像才是我的本意……）
		for(char ch='0';ch<='9';++ch) {//枚举所有位数
			int j=i;
			while(j && s[j+1]!=ch) j=kmp[j];//失配回跳
			if(s[j+1]==ch) j++;//该情况成立
			G.a[i][j]=(G.a[i][j]+1)%mod;//加上一种情况
		}
	}
	F.a[0][0]=1;//F是一行m列的
	G=quickpow(G,n);
	F=F*G;
	int ans=0;
	for(int i=0;i<m;++i) {
		ans=(ans+F.a[0][i])%mod;
	}
	printf("%d",ans);
	return 0;
}