HNOI2008GT考试
阅读原文时间:2023年07月08日阅读:3

题目链接

考虑dp,f(i,j)表示做到了第i位(共n位),当前的后缀串与A1~Aj相匹配 接下来的方案数。转移的话枚举一个k=0~9表示这位选什么,如果选了以后,匹配的位置会改变到 j' ,j'可以通过预处理A串的next数组(就是kmp里面的那个)然后不断向前跳得到,所以f(i,j) = ∑ f(i+1, j')。

发现转移系数与i无关,因此可以用next数组处理出系数矩阵(长宽均为m),再做矩阵快速幂即可。

复杂度O(m^3*logn)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define P puts("lala")
#define cp cerr<<"lala"<'9') {if(ch=='-')g=-1;ch=getchar();}
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar(); return re*g; } typedef long long ll; typedef pair pii;

const int M=25;
struct mat
{
int n,m;
int s[M][M];
mat() {clean();}
void clean() {memset(s,0,sizeof(s));n=m=0;}
};
int mod;

mat operator * (mat a,mat b)
{
mat c;
c.n=a.n; c.m=b.m;
for(int i=0;i>=1,a=a*a) if(n&1) ans=ans*a;
return ans;
}

mat X,V;
char s[M];
int n,m,next[M];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
#endif
int i,j,opt,T;
n=read();m=read();mod=read();
scanf("%s",s+1);
next[1]=0;
int k=0;
for(i=2;i<=m;++i) { while(k>0&&s[k+1]!=s[i]) k=next[k];
if(s[k+1]==s[i]) k++;
next[i]=k;
}
for(i=0;i0&&j!=s[k+1]-48) k=next[k];
if(j==s[k+1]-48) k++;
if(k<m) X.s[i][k]=(X.s[i][k]+1)%mod;
}
}
X.n=X.m=m;
V.n=m; V.m=1;
for(i=0;i<m;++i) V.s[i][0]=1;
X=fpm(X,n);
X=X*V;
printf("%d\n",X.s[0][0]%mod);
return 0;
}
/*

*/

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器