AcWing 1052. 设计密码
原题链接
中等
作者:
wangyj
,
2021-01-17 20:34:38
,
所有人可见
,
阅读 318
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
int n,m,nxt[55],f[55][55],ans=0,i,j,u;
char str[55],k;
int main()
{
scanf("%d%s",&n,str+1);
m=strlen(str+1);
for(i=2,j=0;i<=m;i++){
while(j&&str[i]!=str[j+1])j=nxt[j];
if(str[i]==str[j+1])j++;
nxt[i]=j;
}
f[0][0]=1;
for(i=0;i<n;i++)for(j=0;j<m;j++)for(k='a';k<='z';k++){
u=j;
while(u&&k!=str[u+1])u=nxt[u];
if(k==str[u+1])u++;
if(u<m)f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
}
for(i=0;i<m;i++)ans=(ans+f[n][i])%mod;
printf("%d\n",ans);
return 0;
}