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

xiaoxiao2021-02-28  7

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=0m1dp(n,i) 那么我们可以发现我们令 p(i,j) 表示从不吉利的字符串第i个字符后添加一个数字就可以从i个匹配变成j个匹配的可以填写的数字的个数那么我们显然有 dp(i,j)=k=0m1(dp(i1,k)×p(k,j)) 那么我们的p显然可以进行预处理,那么我们发现p是可以表示成一个矩阵的同时我们发现dp也可以表示成一个矩阵那么我们显然有 DPi=DPi1×P 那么我们就有 DPn=DPn1×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; } 
转载请注明原文地址: https://www.6miu.com/read-1100122.html

最新回复(0)