[BZOJ 1009][HNOI2008]GT考试（KMP+线性齐次递推的矩阵加速？+DP）

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

Solution

---

不是说题目起得长一般会有人看么x

递推，由KMP得到next数组 f[i][j] ：到第 i 的长度时，后缀与s的前缀相同的长度（最长）为 j f[i][j]=∑next[k]=if[i−1][k] 看到N的数据范围，于是可以想到矩阵，快速幂加速 感觉对构造矩阵不是很熟QvQ 这题再想想

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int n,m,Mod; int next[25]; char s[25]; struct Matrix{ int p[25][25]; Matrix(){memset(p,0,sizeof(p));} }a; Matrix operator * (const Matrix& A,const Matrix& B) { Matrix C; for(int i=0;i<m;i++) for(int j=0;j<m;j++) for(int k=0;k<m;k++) { C.p[i][j]+=(A.p[i][k]*B.p[k][j])%Mod; C.p[i][j]%=Mod; } return C; } void getnext() { int j=0; for(int i=2;i<=m;i++) { while(j&&s[j+1]!=s[i])j=next[j]; if(s[j+1]==s[i])j++; next[i]=j; } } void work() { int k; for(int i=0;i<m;i++) for(int j=0;j<=9;j++) { k=i; //前i位已经匹配 while(k&&s[k+1]-'0'!=j)k=next[k]; if(s[k+1]-'0'==j)k++; //由i可以转移到k a.p[k][i]++; } } Matrix Pow(Matrix A,int n) { Matrix res; for(int i=0;i<m;i++) res.p[i][i]=1; while(n>0) { if(n&1)res=res*A; A=A*A; n>>=1; } return res; } int main() { scanf("%d%d%d",&n,&m,&Mod); scanf("%s",s+1); getnext(); work(); a=Pow(a,n); int ans=0; for(int i=0;i<m;i++) ans+=a.p[i][0],ans%=Mod; printf("%d",ans); return 0; }