题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1009
题意概述：
求有多少种方案构造一个长度为N的数字串，使得其中不包含给出的长度为M的数字串（数字串可以包含前导0），答案mod K。
N<=10^9,M<=20,K<=1000.
分析：
首先看到这个东西就想到了字符串+dp的套路......注意到N非常**大（滑稽）可能可以用矩阵快速幂优化一下。
那么构造一个线性的dp方程。
因为只有一个串，那么考虑用KMP来辅助dp。
令f(i,j)表示已经完成构造第i个字符，当前构造字符串和给出的串最长公共后缀前缀长度为j的方案数。
先考虑j!=0，有一种转移方案是f(i-1,j-1)，另外有转移方案为f(i-1,k)，满足S[j-1]是k的fail路径上第一个等于s[j-1]的数字。（因为公共前后缀长度为j的情况下当前字符是唯一确定的，所以所有的转移前面的系数为1）
然后考虑j=0，有一种转移是f(i-1,0)*9，另外有转移f(i-1,k)，前面的系数为k到0的fail路径上没有出现过的数字的数量。
请仔细体会这奥妙无穷的dp......（我要不要这么蠢啊...都不仔细想想...一遍就构造好的话哪里来的这么多事情）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<set> 9 #include<map> 10 #include<vector> 11 #include<cctype> 12 using namespace std; 13 const int maxm=25; 14 15 int N,M,K,f[maxm]; 16 char S[maxm]; 17 struct matrix{ 18 static const int maxn=22; 19 int a[maxn][maxn],r,c; 20 matrix(){ memset(a,0,sizeof(a)); r=c=0; } 21 void init(int len){ 22 r=c=len; 23 for(int i=0;i<r;i++) a[i][i]=1; 24 } 25 friend matrix operator * (matrix x,matrix y){ 26 matrix z; 27 z.r=x.r,z.c=y.c; 28 for(int i=0;i<z.r;i++) 29 for(int j=0;j<z.c;j++) 30 for(int k=0;k<x.c;k++) 31 z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%K; 32 return z; 33 } 34 matrix qkpow(int y){ 35 matrix re,t; 36 re.init(this->r); t=*this; 37 for(int i=0;(1<<i)<=y;i++){ 38 if((1<<i)&y) re=re*t; 39 t=t*t; 40 } 41 return re; 42 } 43 }A,B; 44 45 void getfail(char *t) 46 { 47 f[0]=f[1]=0; 48 int n=strlen(t); 49 for(int i=1;i<n;i++){ 50 int j=f[i]; 51 while(j&&t[i]!=t[j]) j=f[j]; 52 f[i+1]=t[i]==t[j]?j+1:0; 53 } 54 } 55 void work() 56 { 57 scanf("%d%d%d%s",&N,&M,&K,&S); 58 getfail(S); 59 A.r=A.c=M; 60 A.a[0][0]=9; 61 bool vis[10]; 62 for(int i=1;i<M;i++){ 63 memset(vis,0,sizeof(vis)); 64 int p=i; 65 while(p) vis[S[p]-'0']=1,p=f[p]; 66 vis[S[0]-'0']=1; 67 for(int k=0;k<10;k++) 68 if(!vis[k]) A.a[i][0]++; 69 } 70 for(int j=1;j<M;j++){ 71 A.a[j-1][j]=1; 72 for(int i=j;i<M;i++){ 73 int p=i; 74 while(p>j-1){ 75 if(S[p]==S[j-1]) break; 76 p=f[p]; 77 } 78 if(p==j-1) A.a[i][j]=1; 79 } 80 } 81 B.r=1,B.c=M; 82 B.a[0][0]=9,B.a[0][1]=1; 83 B=B*A.qkpow(N-1); 84 int ans=0; 85 for(int j=0;j<M;j++) ans=(ans+B.a[0][j])%K; 86 printf("%d ",ans); 87 } 88 int main() 89 { 90 work(); 91 return 0; 92 }