Description
阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0
Input
第一行输入N,M,K.接下来一行输入M位的数。 100%数据N<=10^9,M<=20,K<=1000 40%数据N<=1000 10%数据N<=6
Output
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.
Sample Input
4 3 100
111
111
Sample Output
81
是个DP，然后我开始想用总个数-不可行个数求，yy了半个小时，不行
题解说这个题f[i][j]=f[i][k]*a[k][j]
a[k][j] 表示从f[i-1][k]转移到f[i][j]的方案数
用kmp构造出初始矩阵表示如果a[i][j]==1则说明i的fail指针指向j，矩阵快速幂就好了
#include<cstdio>
int n,m,mod;
int fail[];
char s[];
int a[][],b[][];
void mul(int a[][],int b[][],int ans[][])
{
int tmp[][];
for(int i=;i<m;i++)
for(int j=;j<m;j++)
{
tmp[i][j]=;
for(int k=;k<m;k++)
tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
}
for(int i=;i<m;i++)
for(int j=;j<m;j++)
ans[i][j]=tmp[i][j];
}
void pre(){
for(int i=;i<m;i++)
for(int j=;j<=;j++){
int t=i;
while(t&&s[t+]-''!=j) t=fail[t];
if(s[t+]-''==j) t++;
b[i][t]++;
}
} void kmp(){
int j=;
for(int i=;i<=m;i++){
while(j>&&s[j+]!=s[i]) j=fail[j];
if(s[j+]==s[i])j++;
fail[i]=j;
}
} int main(){
scanf("%d%d%d%s",&n,&m,&mod,s+);
kmp();
pre();
for(int i=;i<m;i++) a[i][i]=;
while(n)
{
if(n&)mul(a,b,a);
mul(b,b,b);
n>>=;
}
int sum=;
for(int i=;i<m;i++) sum=(a[][i]+sum)%mod;
printf("%d",sum);
}