首页 > 代码库 > BZOJ 1009 【HNOI2008】 GT考试
BZOJ 1009 【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取余的结果.
这道题一眼看去像是一道容斥dp，仔细思考后发现其实普通的dp就可以做了。
我们令fi,j表示准考证号确定了前i位，其中最后一段已经和不吉利串匹配了j位的方案数。那么，显然我们只需要枚举每一位选什么数字即可。至于加了一位数字之后最后一段匹配了多少位，完全可以用kmp来解决。因为kmp算法中next数组的含义就是不为整个串前缀与后缀相等的不为的最大长度。
但是，这样的复杂度是O(N*M^2)的。观察发现，M特别小，于是可以把转移矩阵预处理出来，使用矩阵快速幂优化即可。
下面贴代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 7 8 using namespace std; 9 typedef long long llg;10 11 int n,m,k,nt[22],ans;12 char s[22];13 void gi(int &x){if(x>=k) x%=k;}14 struct matrix{15 int w[23][23];16 matrix(){memset(w,0,sizeof(w));}17 void fu(){for(int i=0;i<m;i++) w[i][i]=1;}18 matrix operator * (const matrix &h)const{19 matrix a;20 for(int i=0;i<m;i++)21 for(int j=0;j<m;j++)22 for(int k=0;k<m;k++)23 a.w[i][j]+=w[i][k]*h.w[k][j],gi(a.w[i][j]);24 return a;25 }26 }A,Aa;27 28 int getint(){29 int w=0;bool q=0;30 char c=getchar();31 while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar();32 if(c==‘-‘) c=getchar(),q=1;33 while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();34 return q?-w:w;35 }36 37 matrix mi(matrix a,int b){38 matrix s; s.fu();39 while(b){40 if(b&1) s=s*a;41 a=a*a; b>>=1;42 }43 return s;44 }45 46 int main(){47 File("a");48 n=getint(); m=getint(); k=getint();49 scanf("%s",s+1);50 for(int i=2,j=0;i<=m;i++){51 while(j && s[j+1]!=s[i]) j=nt[j];52 if(s[j+1]==s[i]) j++;53 nt[i]=j;54 }55 for(int i=0,x;i<m;i++)56 for(int j=0;j<=9;j++){57 x=i;58 while(x && s[x+1]-‘0‘!=j) x=nt[x];59 if(s[x+1]-‘0‘==j) x++;60 if(x<m) A.w[i][x]++;61 }62 Aa=mi(A,n);63 for(int i=0;i<m;i++) ans+=Aa.w[0][i],gi(ans);64 printf("%d",ans);65 }
BZOJ 1009 【HNOI2008】 GT考试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。