【bzoj1009】[HNOI2008]GT考试

时间：2021-01-10 23:39:51

1009: [HNOI2008]GT考试

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 3018  Solved: 1856
[Submit][Status][Discuss]

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
 
 
【题解】
动态规划啊，但数据这么大怎么想得到是动态规划呢，太弱了......
f[i][j]表示准考证前i位中后j位为不吉利的数字的前j位。
转移方程：
     【bzoj1009】[HNOI2008]GT考试
 

【bzoj1009】[HNOI2008]GT考试

因此就可以使用矩阵乘法加速了！

a[k][j]表示f[i-1][k]转为f[i][j]的方法数,这步可以用KMP解决。

ans+=f[0][j] (j=0;j<m;++j);

——转自怡红公子
这题看了一个晚上的题解，然而关于a矩阵的求法还不是太懂，希望大神指教。
===========================================
2016.11.1更新：
A掉2道 AC自动机+矩阵乘法后，这道题就彻底理解了。
代码中的b矩阵表示转移的路径数，然后自乘n次，就相当于是转移n次的路径数。
这个和邻接矩阵的自乘原理是一样的。（floyd）
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 using namespace std;

 int n,m,mod,p[],a[][],b[][];

 char ch[];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

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

 {

     int temp[][];

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

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

         {

             temp[i][j]=;

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

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

         }

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

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

             ans[i][j]=temp[i][j];

 }

 int main()

 {

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

     scanf("%s",ch+);

     int j=;

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

     {

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

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

         p[i]=j;

     }

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

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

         {

             int t=i;

             while(t>&&ch[t+]-''!=j)  t=p[t];

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

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

         }

     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=(sum+a[i][])%mod;

     printf("%d",sum);

     return ;

 }
 
 

相关文章