依旧看人代码写
，不过我觉得自己慢慢写一个也可以写成？
原题：
阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为
0
N<=10^9,M<=20,K<=1000
一开始完全是懵逼的，后来找到两个解释结合一下就理解了
用a(i,j)表示原串走到i，不吉利的串走到j的方案数
设一个数组b(i,j)，表示从(i,j)转移到(i+1,k)的方案数，这个可以用kmp处理，先kmp出next，然后枚举i和j，根据kmp求出k并将b(i+1,k)++
然后这个b表示的就是a中的元素下一步会贡献到哪里
这个东西比较玄，只能勉强意会……
NOIP吧里有一种解释，虽然写法似乎和我的不太一样，引导思路效果不错：
“构造转移矩阵A和列向量B，B=(f[0][0],f[0][1],...,f[0][m])，A可以由DP得到，那么A*B的结果就是(f[1][0],f[1][1],...,f[1][m])，所以A^n*B的结果就是(f[n][0],f[n][1],...,f[n][m])”
然后矩阵快速乘即可
小技巧：使用a&1判断奇偶
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,mo,s[];
int next[];
int b[][],a[][],c[][];
int ans=;
void kmp(){
int temp=; next[]=;
for(int i=;i<=m;i++){
while(temp && s[temp+]!=s[i]) temp=next[temp];
if(s[temp+]==s[i]) temp++;
next[i]=temp;
}
}
void get_b(){
int temp;
for(int i=;i<m;i++){//注意j枚举的是下一位，因为这里j是对下一位的转移，所以矩阵乘法从0开始写，比较方便
a[i][i]=;
for(int j=;j<=;j++){
temp=i;
while(temp && s[temp+]!=j) temp=next[temp];
if(j==s[temp+]) b[i][temp+]+=;
else b[i][]+=;
}
}
}
void fast_mi(){
while(n){
if(n&){//快速判断奇偶
for(int i=;i<m;i++)
for(int j=;j<m;j++){
c[i][j]=;//反正也要枚举，就不用memset了
for(int k=;k<m;k++)
c[i][j]=(c[i][j]+b[i][k]*a[k][j])%mo;
}
for(int i=;i<m;i++)
for(int j=;j<m;j++)
a[i][j]=c[i][j];
}
n>>=;
for(int i=;i<m;i++)
for(int j=;j<m;j++){
c[i][j]=;
for(int k=;k<m;k++)
c[i][j]=(c[i][j]+b[i][k]*b[k][j])%mo;
}
for(int i=;i<m;i++)
for(int j=;j<m;j++)
b[i][j]=c[i][j];
/*for(int i=0;i<m;i++){
for(int j=0;j<m;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}*/
}
}
int main(){//freopen("ddd.in","r",stdin);
memset(b,,sizeof(b));
cin>>n>>m>>mo;
for(int i=;i<=m;i++){
scanf("%c",&s[i]); while(s[i]<''||s[i]>'') scanf("%c",&s[i]);
s[i]-='';
}
kmp(); get_b();
fast_mi();
for(int i=;i<m;i++) ans=(ans+a[][i])%mo;
cout<<ans<<endl;
return ;
}