【BZOJ1009】[HNOI2008]GT考试 next数组+矩阵乘法

【BZOJ1009】[HNOI2008]GT考试

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位的数。 N<=10^9,M<=20,K<=1000

Output

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

Sample Input

4 3 100
111

Sample Output

81

题解：虽然AC自动机的fail和KMP的next只差了那么一点点，但为什么感觉AC自动机比KMP好理解100倍~

好吧我们还是用KMP，先求出next数组，然后用f[i][j]表示i位数，第i位数匹配到了模板串的第j位时的方案数

然后从0..9枚举第i+1位，设加入了第i+1位后匹配到了位置k，则有f[i+1][k]+=f[i][j]

若第i位正好匹配成功，此时k=m，则f[i+1][m]+=f[i][j]

显然我们可以用矩乘来优化这个DP过程，我们令x[i][j]表示经过1次匹配后，从位置i匹配到了位置j的方案数。那么对于上面所有符合条件的(j,k)，我们都令x[j][k]=1，初始ans[0][0]=1。然后ans*=x^N，答案就是∑ans[0][0...m-1]

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

int next[25];

char str[25];

typedef struct matrix

{

	int v[25][25];

}M;

M x,ans,emp;

int n,m,mod,sum;

M mmul(M a,M b)

{

	M c=emp;

	int i,j,k;

	for(i=0;i<=m;i++)

		for(j=0;j<=m;j++)

			for(k=0;k<=m;k++)

				c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;

	return c;

}

void pm(int y)

{

	while(y)

	{

		if(y&1)	ans=mmul(ans,x);

		x=mmul(x,x),y>>=1;

	}

}

int main()

{

	scanf("%d%d%d%s",&n,&m,&mod,str);

	int i=0,j=-1,k;

	next[0]=-1;

	while(i<m-1)

	{

		if(j==-1||str[i]==str[j])	next[++i]=++j;

		else	j=next[j];

	}

	for(i=0;i<m;i++)

	{

		for(j=0;j<=9;j++)

		{

			k=i;

			while(k!=-1&&str[k]-'0'!=j)	k=next[k];

			x.v[i][k+1]++;

		}

	}

	x.v[m][m]=10,ans.v[0][0]=1;

	pm(n);

	for(i=0;i<m;i++)	sum=(sum+ans.v[0][i])%mod;

	printf("%d",sum);

	return 0;

}