「BZOJ1009」[HNOI2008] GT考试

2014年5月9日15,3476

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

Sample Output

题解

矩阵乘法的题题解写起来都十分麻烦。。

而且很多东西只能意会。。

f[i , j]表示前 i 个准考证号匹配到不吉利串第 j 个的方案

然后你需要把一个答案矩阵f[i , j]转移到f[i+1 , j]

举个例子，样例，比如当前匹配到了第2位，也就是说前 i 位的结尾是11

对于第 i+1 个字符，如果是 1 的话，接着匹配到不吉利串第 3 位，不是 1 的话就匹配到第 0 位了

也就是说前 i 位匹配到了不吉利串 j 位，加入 i+1 这个字符，有不同情况，有一些会转移到j+1，一些会转移到其他的，写成一些形如f[i+1 , k] += f[i , j]的式子……

f[i+1 , 3] += f[i , 2]

f[i+1 , 0] += f[i , 2]

即枚举i+1可能出现的字符，然后看n个f[i , j]分别转移到哪去，就在转移矩阵的这个转移路径上+1

按照这个思路用kmp写出转移矩阵，事实上暴力应该就行了

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int n,m,mod;
int p[25];
char ch[25];
int a[25][25],b[25][25];
void mul(int a[25][25],int b[25][25],int ans[25][25])
{
	int tmp[25][25];
	for(int i=0;i<m;i++)
	    for(int j=0;j<m;j++)
	    {
	    	tmp[i][j]=0;
	    	for(int k=0;k<m;k++)
	    	    tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
	    }
	for(int i=0;i<m;i++)
	    for(int j=0;j<m;j++)
	        ans[i][j]=tmp[i][j];
}
int main() 
{
	n=read();m=read();mod=read();
    scanf("%s",ch+1);
    int j=0;
	for(int i=2;i<=m;i++)
    {
    	while(j>0&&ch[j+1]!=ch[i])j=p[j];
    	if(ch[j+1]==ch[i])j++;
    	p[i]=j;
    }
    for(int i=0;i<m;i++)
       for(int j=0;j<=9;j++)
       {
       	    int t=i;
			while(t>0&&ch[t+1]-'0'!=j)
			    t=p[t];
			if(ch[t+1]-'0'==j)t++;
			if(t!=m)b[t][i]=(b[t][i]+1)%mod;
       }
    for(int i=0;i<m;i++)
        a[i][i]=1;
    while(n)
    {
    	if(n&1)mul(a,b,a);
    	mul(b,b,b);
    	n>>=1;
    }
    int sum=0; 
	for(int i=0;i<m;i++)
	    sum=(sum+a[i][0])%mod;
	printf("%d",sum);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

int n,m,mod;

int p[25];

char ch[25];

int a[25][25],b[25][25];

void mul(int a[25][25],int b[25][25],int ans[25][25])

{

int tmp[25][25];

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

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

{

tmp[i][j]=0;

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

tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;

}

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

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

ans[i][j]=tmp[i][j];

}

int main()

{

n=read();m=read();mod=read();

scanf("%s",ch+1);

int j=0;

for(int i=2;i<=m;i++)

{

while(j>0&&ch[j+1]!=ch[i])j=p[j];

if(ch[j+1]==ch[i])j++;

p[i]=j;

}

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

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

{

int t=i;

while(t>0&&ch[t+1]-'0'!=j)

t=p[t];

if(ch[t+1]-'0'==j)t++;

if(t!=m)b[t][i]=(b[t][i]+1)%mod;

}

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

a[i][i]=1;

while(n)

{

if(n&1)mul(a,b,a);

mul(b,b,b);

n>>=1;

}

int sum=0;

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

sum=(sum+a[i][0])%mod;

printf("%d",sum);

return 0;

}

« 「BZOJ1037」[ZJOI2008] 生日聚会Party 「NOIP模拟赛」数列 »

orzorz

请问转移矩阵在前面的时候不会不合法吗。。。比如说dp[i][j]。。如果i的长度小于j的时候呢。。。

Flandre·Scarlet

从dp方程转为矩阵乘法个人觉得不是问题关键。希望黄学长（如果还能再发题解的话）能把dp分析写得更详细些。

hzwer

这个题解我重写过一次了。。。
确实不好理解
我再改改看。？

orz

算最后的ans的时候为什么将a[i,0]累加呢。。在原DP中不应该是加上f[n,0..m-1]?

hzwer

a矩阵是初始矩阵，乘上了转移矩阵b

YJZ

渣渣来膜拜。。

hzwer.com _ Home | http://hzwer.com

「BZOJ1009」[HNOI2008] GT考试

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论