字符串(string)
时间限制: 8 Sec 内存限制: 512 MB
题解:
其实是一道水题,但是考试的时候脑抽了,没有调出来。
dp非常明显啊,dp[i][j][k]表示第i位已经有j个匹配成功如今匹配到第k位。
转移也比较简单,直接在代码里看好了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+3,mod=1e9+7;
int n,m,K,ans,bit[N],fail[8],a[8],dp[N][N][8],p[8][2];
int mo(int x)
{
if(x>mod)x-=mod;
return x;
}
int main()
{
scanf("%d%d%d",&n,&m,&K);
bit[0]=1;
for(int i=1;i<=n;i++)
bit[i]=mo(bit[i-1]<<1);
if(m==0)
{
printf("%d\n",bit[n]);
return 0;
}
n-=K;
if(n<K)
{
puts("0");
return 0;
}
for(int i=0;i<(1<<(K-1));i++)
{
for(int j=1;j<=K;j++)
if(i&bit[j-1])a[j]=1;else a[j]=0;
int t=0;fail[1]=0;
for(int j=2;j<=K;j++)
{
while(t&&a[t+1]!=a[j])t=fail[t];
if(a[t+1]==a[j])t++;
fail[j]=t;
}
for(int j=0;j<K;j++)
{
t=j;
while(t&&a[t+1]!=0)t=fail[t];
if(a[t+1]==0)t++;
p[j][0]=t;
t=j;
while(t&&a[t+1]!=1)t=fail[t];
if(a[t+1]==1)t++;
p[j][1]=t;
}
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int j=0;j<n;j++)
for(int k=0;k<=n;k++)
for(int l=0;l<K;l++)
{
int t;
t=p[l][0];
if(t==K)dp[j+1][(k+1)][fail[K]]=mo(dp[j+1][(k+1)][fail[t]]+dp[j][k][l]);else
dp[j+1][k][t]=mo(dp[j+1][k][t]+dp[j][k][l]);
t=p[l][1];
if(t==K)dp[j+1][(k+1)][fail[K]]=mo(dp[j+1][(k+1)][fail[t]]+dp[j][k][l]);else
dp[j+1][k][t]=mo(dp[j+1][k][t]+dp[j][k][l]);
}
for(int k=m;k<=n;k++)
for(int l=0;l<K;l++)ans=mo(ans+dp[n][k][l]);
}
ans=mo(ans*2);
printf("%d\n",ans);
return 0;
}