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取余的结果.
Sample Input
4 3 100 111
Sample Output
81
【解题报告】
首先我们令 dp(i,j) 表示当前我们枚举到第i位的时候我们枚举的后缀最长和不吉利的字符串的前缀已经匹配了j个的时候的方案数量，那么我们的答案就是 ∑i=0m−1dp(n,i) 那么我们可以发现我们令 p(i,j) 表示从不吉利的字符串第i个字符后添加一个数字就可以从i个匹配变成j个匹配的可以填写的数字的个数那么我们显然有 dp(i,j)=∑k=0m−1(dp(i−1,k)×p(k,j)) 那么我们的p显然可以进行预处理，那么我们发现p是可以表示成一个矩阵的同时我们发现dp也可以表示成一个矩阵那么我们显然有 DPi=DPi−1×P 那么我们就有 DPn=DPn−1×P=DP0×Pn 使用矩阵加速进行优化
代码如下：
/************************************************************** Problem: 1009 User: onepointo Language: C++ Result: Accepted Time:56 ms Memory:1952 kb ****************************************************************/ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 50 int n,m; int MOD,Fail[N]; char s[N]; struct Matrix { int Ma[N][N],n,m; void Clear(int u,int un,int um) { n=un,m=um; memset(Ma,0,sizeof(Ma)); if(u) for(int i=0;i<un;++i) Ma[i][i]=1; } Matrix operator * (const Matrix &ma) { Matrix ret; ret.Clear(0,n,m); for(int i=0;i<n;++i) for(int j=0;j<ma.m;++j) for(int k=0;k<ma.n;k++) { ret.Ma[i][j]+=Ma[i][k]*ma.Ma[k][j]; ret.Ma[i][j]%=MOD; } return ret; } }; Matrix Mpow(Matrix m,int p) { Matrix ret; if(p==0) { ret.Clear(1,2,2); return ret; } else if(p==1) return m; ret=Mpow(m,p/2); if(p%2==0) return ret*ret; return (ret*ret)*m; } int main() { scanf("%d%d%d",&n,&m,&MOD); scanf("%s",s+1); Matrix mtr; mtr.Clear(0,m,m); mtr.Ma[0][0]=9;mtr.Ma[0][1]=1; for(int i=1;i<m;++i) { int us=Fail[i]; while(us) { if(s[us+1]==s[i+1]) break; us=Fail[us]; } if(s[us+1]==s[i+1]) Fail[i+1]=us+1; else Fail[i+1]=0; for(int j=0;j<=9;++j) { int u=i; while(u&&s[u+1]!=j+'0') u=Fail[u]; if(s[u+1] == j+'0') mtr.Ma[i][u+1]=(mtr.Ma[i][u+1]+1)%MOD; else mtr.Ma[i][0]=(mtr.Ma[i][0]+1) % MOD; } } Matrix ans=Mpow(mtr,n); int cnt=0; for(int i=0;i<m;++i) (cnt+=ans.Ma[0][i])%MOD; printf("%d\n",(cnt+MOD)%MOD); return 0; } 