题目描述

给我们一个数字串的集合和一个正数N,让我们求出所有不超过N的幸运数个数.
幸运数:不包含数字串的集合中的任何一个串为子串

样例

输入

20
3
2
3
14

输出

14

分析

数位DP+AC自动机
用dp[i][j][k][l]表示枚举到第i位,匹配到AC自动机的第j个节点,是否为全0串,是否是N的前缀的个数
如果k==1即当前状态是全0串,则j只能是0,不能在其它节点瞎跳
如果l==1即当前是N的前缀,则枚举下一位时不能超过N对应位上的数字

AC自动机+数位DP

#include<bits/stdc++.h>
using namespace std;
const int N = 1510,mod = 1e9+7;
int tr[N][10],st[N],idx;
int fail[N],q[N];
int dp[N][N][2][2];
int n,m;
char s[N],T[N];
void insert()
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'0';
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
    st[u]=1;
}
void build()
{
    int hh=0,tt=0;
    for(int i=0;i<10;i++)
        if(tr[0][i])q[tt++]=tr[0][i];
    while(hh!=tt)
    {
        int t=q[hh++];
        for(int i=0;i<10;i++)
        {
            int u=tr[t][i];
            if(!u)tr[t][i]=tr[fail[t]][i];
            else
            {
                fail[u]=tr[fail[t]][i];
                q[tt++]=u;
                st[u]|=st[fail[u]];
            }
        }
    }
}
int main()
{
    cin>>T+1>>m;
    for(int i=1;i<=m;i++)
    {    
        cin>>s;
        insert();
    }
    build();
    n=strlen(T+1);
    dp[0][0][1][1]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<=idx;j++)
            for(int k=0;k<2;k++)
            {
                if(k==1&&j!=0)continue;
                for(int l=0;l<2;l++)
                {
                    if(dp[i][j][k][l]==0)continue;
                    if(l==1)//是前缀
                    {
                        for(int p=0;p<=T[i+1]-'0';p++)
                        {
                            if(k==0)//不是全0
                            {
                                int u=tr[j][p];
                                if(st[u])continue;
                                if(p!=T[i+1]-'0')dp[i+1][u][0][0]=(dp[i+1][u][0][0]+dp[i][j][k][l])%mod;
                                else dp[i+1][u][0][1]=(dp[i+1][u][0][1]+dp[i][j][k][l])%mod;                                
                            }
                            else//全0
                            {
                                if(p==0)dp[i+1][0][1][0]=(dp[i+1][0][1][0]+dp[i][j][k][l])%mod;
                                else
                                {
                                    int u=tr[0][p];
                                    if(st[u])continue;   
                                    if(p!=T[i+1]-'0')dp[i+1][u][0][0]=(dp[i+1][u][0][0]+dp[i][j][k][l])%mod;
                                    else dp[i+1][u][0][1]=(dp[i+1][u][0][1]+dp[i][j][k][l])%mod;  
                                }
                            }
                        }
                    }
                    else//不是前缀
                    {
                        for(int p=0;p<10;p++)
                        {
                            if(k==1)//全0
                            {
                                if(p==0)dp[i+1][0][1][0]=(dp[i+1][0][1][0]+dp[i][j][k][l])%mod;
                                else
                                {
                                    int u=tr[0][p];
                                    if(st[u])continue;   
                                    dp[i+1][u][0][0]=(dp[i+1][u][0][0]+dp[i][j][k][l])%mod;
                                }
                            }
                            else
                            {
                                int u=tr[j][p];
                                if(st[u])continue;
                                dp[i+1][u][0][0]=(dp[i+1][u][0][0]+dp[i][j][k][l])%mod;
                            }
                        }
                    }
                }
            }
    int res=0;
    for(int i=0;i<=idx;i++)
        for(int j=0;j<2;j++)
            res=(res+dp[n][i][0][j])%mod;
    cout<<res;
    return 0;
}