【bzoj1009】: [HNOI2008]GT考试
先用kmp写个暴力
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char s[];
int n,m,p,fail[],f[][]; void kmp(){
fail[]=;
for (int i=;i<=m;i++){
fail[i]=fail[i-];
if (s[fail[i-]]==s[i-]) fail[i-]=fail[fail[i-]];
while (s[fail[i]]!=s[i-] && fail[i]) fail[i]=fail[fail[i]];
fail[i]++;
}
} int main(){
scanf("%d%d%d",&n,&m,&p);
scanf("%s",s+);
kmp();
f[][]=;
for (int i=;i<=n;i++){
for (int j=;j<m;j++){
for (int k='',now=j+;k<='';k++,now=j+){
while (k!=s[now] && now) now=fail[now];
f[i][now]=(f[i][now]+f[i-][j])%p;
}
}
}
int ans=;
for (int i=;i<m;i++){
ans=(ans+f[n][i])%p;
}
printf("%d\n",ans);
return ;
}
暴力
然后对着转移方程yy一下矩阵就好辣
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char s[];
int n,m,p,fail[];
struct MAT{
int m[][];
int x,y;
}m1,m2; MAT operator * (const MAT &a,const MAT &b){
MAT c;
c.x=b.x,c.y=a.y;
for (int i=;i<=c.x;i++){
for (int j=;j<=c.y;j++){
c.m[i][j]=;
for (int k=;k<=b.y;k++){
c.m[i][j]=(c.m[i][j]+a.m[k][j]*b.m[i][k])%p;
}
}
}
return c;
} int sum(MAT a){
int ans=;
for (int i=;i<=a.x;i++){
for (int j=;j<=a.y;j++){
ans=(ans+a.m[i][j])%p;
}
}
return ans;
} void kmp(){
fail[]=;
for (int i=;i<=m;i++){
fail[i]=fail[i-];
if (s[fail[i-]]==s[i-]) fail[i-]=fail[fail[i-]];
while (s[fail[i]]!=s[i-] && fail[i]) fail[i]=fail[fail[i]];
fail[i]++;
}
} MAT qpow(int x){
for (;x;x=(x>>),m2=m2*m2) if (x&) m1=m1*m2;
return m1;
} int main(){
scanf("%d%d%d",&n,&m,&p);
scanf("%s",s+);
kmp();
m1.x=m;m1.y=;m1.m[][]=;
m2.x=m2.y=m;
for (int i=;i<=m;i++) m1.m[i][]=;
for (int i=;i<=m;i++) for (int j=;j<=m;j++) m2.m[i][j]=;
for (int j=;j<m;j++){
for (int k='',now=j+;k<='';k++,now=j+){
while (k!=s[now] && now)now=fail[now];
m2.m[now+][j+]++;
}
}
printf("%d\n",sum(qpow(n)));
return ;
}
正解
为什么感觉自己的kmp写的好奇怪。。
