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，如需转载请自行联系原作者