这题本来第一个反应是数位dp 然而看到n这么大- - 管他呢照样数位dp 矩阵快速幂优化一下就好了

这道题的关键 是 利用kmp算法 构建转移矩阵

定义f[i][j]表示 i位的数字的最后j位 和不吉利数字的开始j位相同 的方案数有多少，然后我们就开始想转移方程，然而 这转移不是和给出的数字串有关吗……(其实我本来以为是f[i][j]=f[i-1][j-1]+9*f[i-1][j+1]的,打好之后发现样例都过不去……) 。既然字符串给出了 那我们一定可以用奇技淫巧弄出转移的方程 ——对就是kmp

我们用kmp算法匹配的时候 是不断的用fail指针跳转 直到匹配成功为止 在这里我们用相同的方法处理

对于某一个匹配长度k，我们枚举这个位置的数字i 然后进行匹配 fail指针不断的回跳 直到匹配成功或者跳出了字符串 这时候 我们就知道 匹配长度为k的字符串 在添加一个数字i之后 可以转移到哪个位置，转移矩阵中的对应位置++即可。这样就构造成功了转移矩阵，接下来就是用矩阵快速幂随便搞一下,把f[n][0]到f[n][m-1]加起来模一下就是答案了

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,mod,s[30],f[30],nxt[30],sum;
struct mat{
	int a[30][30];
	void reset(){for(int i=0;i<30;i++) for(int j=0;j<30;j++) a[i][j]=0;}
	void set1(){reset();for(int i=0;i<=29;i++) a[i][i]=1;}
	friend mat operator *(mat x,mat y){
		mat z;
		z.reset();
		for(int i=0;i<=20;i++)
			for(int j=0;j<=20;j++)
				for(int k=0;k<=20;k++) (z.a[i][j]+=x.a[i][k]*y.a[k][j])%=mod;
		return z;
	}
}st,zy,ans;
void get(){
	int p;
	f[0]=0;f[1]=0;
	for(int i=2;i<=m;i++) {
		p=f[i-1];
		while(s[p]!=s[i-1] && p) p=f[p];
		f[i]= s[p]==s[i-1]?p+1:0;
	}
	for(int i=0;i<m;i++)
		for(int j=0;j<=9;j++) {
			if(j==s[i]) {zy.a[i][i+1]++;continue;}
			int p=f[i];
			while(s[p]!=j && p) p=f[p];
			if(s[p]==j) zy.a[i][p+1]++;else zy.a[i][0]++;
		}
}
int main(){
	//freopen("1009.in","r",stdin);freopen("1009.out","w",stdout);
	scanf("%d%d%d\n",&n,&m,&mod);
	for(int i=0;i<m;i++) s[i]=getchar()-'0';
	get();
	ans.set1();
	st.a[0][0]=1;
	for(;n;n>>=1){if(n&1)ans=ans*zy;zy=zy*zy;}
	st=st*ans;
	for(int i=0;i<m;i++) (sum+=st.a[0][i])%=mod;
	printf("%d",sum);
	return 0;
}