2017.8.7 GT考试 思考记录

大部分都想出来了，就是不会kmp生成矩阵、

首先要明白kmp失配里面是什么的位置，，，它是和它本身匹配的数，所以比较要用j+1！

然后枚举i的时候枚举的是前面的数都匹配的数再加上一个，所以枚举0~9统计所有结果扔到矩阵里

注意a矩阵一开始要赋初值  n=1的情况，不然输出0

矩阵：

样例的矩阵：

码：

#include<iostream>
#include<cstdio>
using namespace std;
char ch[55];
struct jz
{
int c,k;
int p[25][25];		
}a,b,u,v;
int ans,i,j,K,n,m,sp[25],l;
jz operator *(jz x,jz y)
{
	int i,j,k;
  for(i=0;i<=x.k;i++)
  for(j=0;j<=y.c;j++)
  u.p[i][j]=0;
  	u.k=x.k;
	u.c=x.c;
  for(i=0;i<=x.k;i++)
  for(j=0;j<=x.c;j++) 
  for(k=0;k<=y.c;k++)
	u.p[i][k]=(u.p[i][k]+x.p[i][j]*y.p[j][k])%K;
	return u;
}
jz operator ^(jz x,int ci)
{
	int i,j,k;
	v.k=x.k;
	v.c=x.c;
  for(i=0;i<=x.k;i++)
  for(j=0;j<=x.c;j++)
  if(i==j)v.p[i][i]=1;else v.p[i][j]=0;
	while(ci)
	{
	if(ci&1)v=v*x;	
		ci>>=1;
		x=x*x;		
	}
	return v;
}
int main(){
scanf("%d%d%d",&n,&m,&K);
scanf("%s",ch+1);
	n--;
	j=0;
	for(i=2;i<=m;i++)
	{
		while(j>0&&ch[j+1]!=ch[i])j=sp[j];
		if(ch[j+1]==ch[i])++j;
		sp[i]=j;
	}
	for(i=0;i<m;i++)
	for(l=0;l<=9;l++)
	{
	    j=i;	
		while(j!=0&&ch[j+1]-'0'!=l)j=sp[j];
		if(ch[j+1]-'0'==l)b.p[j+1][i]++;
		else b.p[0][i]++;
	}
   b.c=m;
   b.k=m;
   a.c=0;
   a.k=m;
   a.p[0][0]=9;
   a.p[1][0]=1;
   a=(b^n)*a;
   for(i=0;i<m;i++)
   ans+=a.p[i][0],ans%=K;
   printf("%d",ans);	
}