【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

题解：虽然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;}

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

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ1009】[HNOI2008]GT考试 next数组+矩阵乘法