【BZOJ3530】數數（AC自動機，動态規劃）

題面

BZOJ

題解

很套路的 AC 自動機+ DP

首先，如果長度小于 N

就不存在任何限制

直接大力DP

然後強制限制不能走到帶有标記的點上面

如果長度恰好為 N 的長度

那麼，要考慮是否恰好卡在範圍裡面

于是DP狀态多記一維

表示是否卡在範圍裡面

最後求一下和就行啦

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 2000
#define MOD 1000000007
struct Node
{
    int vis[];
    int lt,fail;
}t[MAX];
int tot,m;
char N[MAX],ch[MAX];
int f[MAX][MAX][],g[MAX][MAX];
void insert(char *s)
{
    scanf("%s",s+);
    int l=strlen(s+),now=;
    for(int i=;i<=l;++i)
    {
        if(!t[now].vis[s[i]-])
            t[now].vis[s[i]-]=++tot;
        now=t[now].vis[s[i]-];
    }
    t[now].lt=;
}
void GetFail()
{
    queue<int> Q;
    for(int i=;i<=;++i)
        if(t[].vis[i])Q.push(t[].vis[i]);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        t[u].lt|=t[t[u].fail].lt;
        for(int i=;i<=;++i)
            if(t[u].vis[i])
                t[t[u].vis[i]].fail=t[t[u].fail].vis[i],Q.push(t[u].vis[i]);
            else t[u].vis[i]=t[t[u].fail].vis[i];
    }
}
int main()
{
    scanf("%s",N+);
    scanf("%d",&m);
    while(m--)insert(ch);
    GetFail();
    int l=strlen(N+);
    long long ans=;
    g[][]=;
    for(int i=;i<l;++i)
        for(int u=;u<=tot;++u)
            if(!t[u].lt)
            {
                for(int k=;k<=;++k)
                    if(!t[t[u].vis[k]].lt)
                    {
                        if(!i&&!k)continue;
                        (g[i+][t[u].vis[k]]+=g[i][u])%=MOD;
                    }
            }
    for(int i=;i<l;++i)
        for(int j=;j<=tot;++j)
            ans=(ans+g[i][j])%MOD;
    f[][][]=;
    for(int i=;i<l;++i)
        for(int u=;u<=tot;++u)
            if(!t[u].lt)
            {
                for(int k=;k<=;++k)
                    if(!t[t[u].vis[k]].lt)
                    {
                        if(!i&&!k)continue;
                        (f[i+][t[u].vis[k]][]+=f[i][u][])%=MOD;
                        if(k<N[i+]-)(f[i+][t[u].vis[k]][]+=f[i][u][])%=MOD;
                        if(k==N[i+]-)(f[i+][t[u].vis[k]][]+=f[i][u][])%=MOD;
                    }
            }
    for(int i=;i<=tot;++i)
        ans=(ans+f[l][i][])%MOD,ans=(ans+f[l][i][])%MOD;
    printf("%lld\n",ans);
    return ;
}