标题效果:给定的长度m数字字符串s。求不包括子s长度n数字串的数目
n<=10^9 看这个O(n)它与
我们不认为这 令f[i][j]长度i号码的最后的字符串j位和s前者j数字匹配方案
例如,当s至12312时间 f[i][3]它表示的长度i。123结尾且不包括子串”12312“的方案数
a[x][y]为f[i-1][x]转移至f[i][y]的方案数
换句话说(可能描写叙述不清楚) a[x][y]为s的长度为x的前缀加上一个数字后 后缀能够与最长长度为y的前缀匹配 这个数字能够有多少种
比方说12312 这个数字串生成的a数组为(数组从0開始):
9 1 0 0 0 0
8 1 1 0 0 0
8 1 0 1 0 0
9 0 0 0 1 0
8 1 0 0 0 1
a[2][1]=1 表示长度为2的前缀加上一个'1'之后最多与长度为1的前缀匹配
a[4][0]=8 表示长度为4的前缀加上'1''2'以外的数就变成了长度为0的前缀
可是a[x][5]表示全然匹配,不满足要求的题意,所以我们矩阵乘法时不考虑这一列
我们发现f[i-1]乘上这个矩阵就变成了f[i] 这个矩阵怎么求呢?KMP算法,对于每一个长度的前缀枚举下一个字符进行转移 详细写法详见代码
f初值是f[0][0]=1,f[0][x]=0 (x>0)
于是最后我们仅仅须要取答案矩阵的第一行就可以
n<=10^9 看这个O(n)它与
我们不认为这 令f[i][j]长度i号码的最后的字符串j位和s前者j数字匹配方案
例如,当s至12312时间 f[i][3]它表示的长度i。123结尾且不包括子串”12312“的方案数
a[x][y]为f[i-1][x]转移至f[i][y]的方案数
换句话说(可能描写叙述不清楚) a[x][y]为s的长度为x的前缀加上一个数字后 后缀能够与最长长度为y的前缀匹配 这个数字能够有多少种
比方说12312 这个数字串生成的a数组为(数组从0開始):
9 1 0 0 0 0
8 1 1 0 0 0
8 1 0 1 0 0
9 0 0 0 1 0
8 1 0 0 0 1
a[2][1]=1 表示长度为2的前缀加上一个'1'之后最多与长度为1的前缀匹配
a[4][0]=8 表示长度为4的前缀加上'1''2'以外的数就变成了长度为0的前缀
可是a[x][5]表示全然匹配,不满足要求的题意,所以我们矩阵乘法时不考虑这一列
我们发现f[i-1]乘上这个矩阵就变成了f[i] 这个矩阵怎么求呢?KMP算法,对于每一个长度的前缀枚举下一个字符进行转移 详细写法详见代码
f初值是f[0][0]=1,f[0][x]=0 (x>0)
于是最后我们仅仅须要取答案矩阵的第一行就可以
去网上找了一堆题解才看懂0.0 这里写的略微具体一点吧
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct matrix{ int xx[22][22]; int* operator [] (int x) { return xx[x]; } }a,b; int n,m,p,ans; char s[100]; int next[100]; void operator *= (matrix &x,matrix &y) { int i,j,k; matrix z; memset(&z,0,sizeof z); for(i=0;i<m;i++) for(j=0;j<m;j++) for(k=0;k<m;k++) z[i][j]+=x[i][k]*y[k][j],z[i][j]%=p; x=z; } void KMP() { int i,fix=0; char j; for(i=2;i<=m;i++) { while( fix && s[fix+1]!=s[i] ) fix=next[fix]; if( s[fix+1]==s[i] ) ++fix; next[i]=fix; } for(i=0;i<m;i++) for(j='0';j<='9';j++) { fix=i; while( fix && s[fix+1]!=j ) fix=next[fix]; if( j==s[fix+1] ) b[i][fix+1]++; else b[i][0]++; } } void Quick_Power(int x) { while(x) { if(x&1)a*=b; b*=b; x>>=1; } } int main() { int i; cin>>n>>m>>p; scanf("%s",s+1); KMP(); for(i=0;i<m;i++) a[i][i]=1; Quick_Power(n); for(i=0;i<m;i++) ans+=a[0][i],ans%=p; cout<<ans<<endl; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4679508.html,如需转载请自行联系原作者