本文主要是介绍【HNOI2008】bzoj1009 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取余的结果.
用 1×m 的向量 a 表示处理了若干位以后,当前匹配了模式串的前
每次用一个 m×m 的矩阵 B 转移,由前
可以把矩阵 B 看成计数器,如果当前匹配了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,p,next[25];
char s[25];
struct mat
{int a[25][25];void I(){for (int i=0;i<m;i++)for (int j=0;j<m;j++)a[i][j]=(i==j);}mat operator * (const mat &mm) const{mat ret;for (int i=0;i<m;i++)for (int j=0;j<m;j++){ret.a[i][j]=0;for (int k=0;k<m;k++)ret.a[i][j]=(ret.a[i][j]+a[i][k]*mm.a[k][j]%p)%p;}return ret;}mat pow(int x){mat ret,base;ret.I();for (int i=0;i<m;i++)for (int j=0;j<m;j++)base.a[i][j]=a[i][j];while (x){if (x&1) ret=ret*base;base=base*base;x>>=1;}return ret;}void init(){int x;for (int i=2,j=0;i<=m;i++){while (j&&s[i]!=s[j+1]) j=next[j];if (s[i]==s[j+1]) j++;next[i]=j;}for (int i=0;i<m;i++)for (int j=0;j<=9;j++){x=i;while (x&&s[x+1]!=j+'0') x=next[x];if (s[x+1]==j+'0') x++;a[i][x]++;}}
}a,b;
int main()
{int ans=0;scanf("%d%d%d",&n,&m,&p);scanf("%s",s+1);a.init();b=a.pow(n);for (int i=0;i<m;i++) ans=(ans+b.a[0][i])%p;printf("%d\n",ans);
}
这篇关于【HNOI2008】bzoj1009 GT考试的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!