首页 > 代码库 > bzoj1009 [HNOI2008]GT考试
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位的数。 100%数据N<=10^9,M<=20,K<=1000 40%数据N<=1000 10%数据N<=6
Output
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.
Sample Input
4 3 100
111
111
Sample Output
81
首先看到不能有某一子串存在就想到kmp
令f[i][j]表示i位的数字，kmp匹配到限制子串的第j位，有多少种方案
如果j==m，那么包含了这个子串。这状态就是没意义的。
怎么转移？注意到f[i][j]能转移到的只有f[i+1][j],f[i+1][next[j]]，f[i+1][next[next[j]]]……
像通常kmp做法那样令j=i，然后while(j){f[i+1][j]=balabala，j=next[j]}
这样当然是对的，但是n=10e的大数据根本过不了
这样当然是对的，但是n=10e的大数据根本过不了
考虑用for去掉第一维i，把第二维的f[j]扔进1*m的矩阵中，然后通过转移我们可以得到i+1时的f[j]。这样一来就可以矩阵快速幂
预处理b数组[x][y]表示从f[i][x]转移到f[i+1][y]的时候要算几个f[i][x]。这个计算也跟上面while (j)balalbala的一样
#include<cstdio>int next[30];int n,m,mod,ans;char s[30];int a[30][30],b[30][30];inline void mult(int a[30][30],int b[30][30],int res[30][30]){ int dat[30][30]; for (int i=0;i<m;i++) for (int j=0;j<m;j++) { dat[i][j]=0; for (int k=0;k<m;k++) dat[i][j]+=a[i][k]*b[k][j]; dat[i][j]%=mod; } for(int i=0;i<m;i++) for (int j=0;j<m;j++) res[i][j]=dat[i][j];}inline void kmp(){ int j=0; for (int i=2;i<=m;i++) { while (j>0 && s[j+1]!=s[i])j=next[j]; if (s[j+1]==s[i])j++; next[i]=j; }}inline void get_matrix(){ for (int i=0;i<m;i++) for (int j=0;j<10;j++) { int now=i; while (now>0 && s[now+1]-‘0‘!=j) now=next[now]; if (s[now+1]-‘0‘==j)now++; if (now!=m)b[now][i]=(b[now][i]+1)%mod; } for (int i=0;i<m;i++)a[i][i]=1;}inline void quickpow(){ while (n) { if (n&1)mult(a,b,a); mult(b,b,b); n>>=1; }}int main(){ scanf("%d%d%d",&n,&m,&mod); scanf("%s",s+1); kmp(); get_matrix(); quickpow(); for (int i=0;i<m;i++)ans+=a[i][0]; printf("%d\n",ans%mod); return 0;}
bzoj1009 [HNOI2008]GT考试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。