比较神仙的$dp+KMP+Matrix$综合题目,比较值得一写
$0x00$:首先我打了一个爆搜
不过对正解并无任何启发。。。(逗比发言请忽略)
$0x01$:基础$dp$
状态还是比较好设的,
考虑设$f_{i,j}$表示$dp$到长串的第$i$位,匹配了短串的前缀长度为$j$时的总方案数
直接转移不大好搞,那么我们还需要一个转移数组
设$g_{k,j}$表示在 和短串匹配长度为$k$的串 后面添加一个字符,使新构成的串 和短串匹配长度为$j$,这样的字符的添加方案数
这个东西可以用$KMP$求,具体而言就是枚举每一种长度以及每一种可能的添加字符,
如果这个字符与短串不匹配,那么就跳$nxt$数组找到合法的最长匹配前缀。
那么转移为$f_{i,j}=\sum_{k=0}^{m-1} f_{i-1,k}*g_{k,j}$那么最终的答案就是$\sum_{i=0}^{m-1} f_{n,i}$,然而复杂度$O(nm^2)$直接爆炸
$0x02$:矩阵优化
我们看到这个方程式非常的像矩阵乘法,考虑矩阵加速递推,经过观察,我们发现这个$f$数组貌似可以省去,直接递推$g^n$就可以得到最后的$f_n$
这样,最后的答案就是$\sum_{i=0}^{m-1}g^n_{0,i}$,时间复杂度$O(m^3log_n)$完全可过
1 #include<bits/stdc++.h> 2 using namespace std; 3 namespace AE86{ 4 inline int read(){ 5 int x=0,f=1;char ch=getchar(); 6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 8 }inline void write(int x,char opt='\n'){ 9 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-'); 10 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 11 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 12 }using namespace AE86; 13 const int NN=1e5+5; 14 int n,m,mod,nxt[NN],ans; 15 char s[25]; 16 namespace Matrix{ 17 struct Ma{ 18 int p[25][25]; 19 inline void cle(){memset(p,0,sizeof(p));} 20 inline void pre(){for(int i=0;i<m;i++)p[i][i]=1;} 21 inline void print(){for(int i=0;i<m;i++){for(int j=0;j<m;j++){cout<<p[i][j]<<" ";} cout<<endl;}} 22 }; 23 inline Ma mul(Ma a,Ma b){ 24 Ma c;c.cle(); 25 for(int i=0;i<m;i++) 26 for(int j=0;j<m;j++) 27 for(int k=0;k<m;k++) 28 (c.p[i][j]+=1ll*a.p[i][k]*b.p[k][j]%mod)%=mod; 29 return c; 30 } 31 inline Ma qmo(Ma a,int b){ 32 Ma c; c.cle(); c.pre(); 33 while(b){ 34 if(b&1) c=mul(c,a); 35 b>>=1; a=mul(a,a); 36 } return c; 37 } 38 inline Ma kmp(){ 39 nxt[1]=0; Ma a; a.cle(); 40 for(int i=2,j=0;i<=m;i++){ 41 while(j && s[j+1]!=s[i]) j=nxt[j]; 42 if(s[j+1]==s[i]) ++j; 43 nxt[i]=j; 44 } 45 for(int i=0;i<m;i++){ 46 for(int ch='0';ch<='9';ch++){ 47 int j=i; 48 while(j && s[j+1]!=ch) j=nxt[j]; 49 if(s[j+1]==ch) ++j; 50 ++a.p[i][j]; 51 } 52 } 53 return a; 54 } 55 }using namespace Matrix; 56 namespace WSN{ 57 inline short main(){ 58 n=read(); m=read(); mod=read(); scanf("%s",s+1); 59 Ma a=kmp(); a=qmo(a,n); 60 for(int i=0;i<m;i++) (ans+=a.p[0][i])%=mod; 61 write(ans); 62 return 0; 63 } 64 } 65 signed main(){return WSN::main();}GT考试