# BZOJ 1009 KMP+矩阵快速幂优化DP

xiaoxiao2021-02-28  7

1009: [HNOI2008]GT考试

Description

Input

Output

Sample Input

4 3 100 111

Sample Output

81

【解题报告】

/************************************************************** 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; } ﻿