首页 > 代码库 > BZOJ1009 HNOI2008 GT考试 一般DP+矩阵乘法+KMP
BZOJ1009 HNOI2008 GT考试 一般DP+矩阵乘法+KMP
题意：给定一个长度为M的字符串A，求长度为N的字符串中，子串中不包含A的字符串的数量，其中字符串仅由‘0’-‘9’组成。
题解：设f[i][j]=长度为i最后几位能匹配A的前j个字符的字符串种数，那么每往后添加一个字符，能转移到的位置通过KMP的Next数组很轻松就能找到。那么我们就能构造出来一个矩阵，a[i][j]=1表示可以通过在A[i]后面加一个字符，使得A[1]-A[j]成为原有字符串的子串。快速幂优化后答案就是f[N][0]+……+f[N][M-1]
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=20+2;int N,M,Fail[MAXN];char A[MAXN];ll K,Ans;struct MATRIX{ ll m[MAXN][MAXN]; int l,r; void Init(){ l=r=0; memset(m,0,sizeof(m)); } MATRIX operator*(MATRIX a){ MATRIX ret; ret.Init(); ret.l=l,ret.r=a.r; for(int i=0;i<ret.l;i++) for(int j=0;j<ret.r;j++) for(int k=0;k<r;k++) ret.m[i][j]=(ret.m[i][j]+m[i][k]*a.m[k][j]%K)%K; return ret; } MATRIX operator^(int x){ MATRIX t,a; a.l=t.l=l,a.r=t.r=r; memcpy(a.m,m,sizeof(a.m)); if(x&1) memcpy(t.m,m,sizeof(t.m)); else for(int i=0;i<l;i++) for(int j=0;j<r;j++) t.m[i][j]=(i==j); while(x>>=1){ a=a*a; if(x&1) t=a*t; } return t; }}T;int main(){ cin >> N >> M >> K; scanf("%s",A+1); for(int i=2,j=0;i<=M;i++){ while(j && A[j+1]!=A[i]) j=Fail[j]; if(A[j+1]==A[i]) j++; Fail[i]=j; } for(int i=0;i<M;i++) for(int j=0;j<=9;j++){ int p=i; while(p && A[p+1]-‘0‘!=j) p=Fail[p]; if(A[p+1]-‘0‘==j) p++; if(p!=M) T.m[p][i]++; } T.l=T.r=M; T=T^N; for(int i=0;i<M;i++) Ans=(Ans+T.m[i][0])%K; cout << Ans << endl; return 0;}
BZOJ1009 HNOI2008 GT考试 一般DP+矩阵乘法+KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。