[Sdoi2014]数数[数位dp+AC自动机]

3530: [Sdoi2014]数数

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 834  Solved: 434
[Submit][Status][Discuss]

Description

我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。
    给定N和S，计算不大于N的幸运数个数。

Input

输入的第一行包含整数N。
    接下来一行一个整数M，表示S中元素的数量。
    接下来M行，每行一个数字串，表示S中的一个元素。

Output

输出一行一个整数，表示答案模109+7的值。

Sample Input

20
3
2
3
14

Sample Output

14

HINT

下表中l表示N的长度，L表示S中所有串长度之和。

1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500

Source

Round 1 day 1

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=;

const int mod=1e9+;

int n,m,len,cnt=,b[N],c[N],w[N],fail[N],tr[N][],q[N];

char a[N];

int f[N][N][];ll ans;

inline void insert(int *s){

    int now=;

    for(int i=;i<=len;i++){

        if(!tr[now][s[i]]) tr[now][s[i]]=++cnt;

        now=tr[now][s[i]];

    }

    w[now]++;

}

inline void AC_mach(){

    for(int i=;i<=;i++) tr[][i]=;

    int p,h=,t=;q[t]=;fail[]=;

    while(h!=t){

        int now=q[++h];

        for(int i=;i<=;i++){

            if(tr[now][i]){

                for(p=fail[now];!tr[p][i];p=fail[p]);

                fail[tr[now][i]]=tr[p][i];

                q[++t]=tr[now][i];

            }

        }

    }

}

inline void dp(int T){

    for(int i=,p;i<=cnt;i++){

        for(int l=;l<=;l++){

            if(w[i]||!f[T-][i][l]) continue;

            for(int j=;j<=;j++){

                for(p=i;!tr[p][j];p=fail[p]);

                f[T][tr[p][j]][l+j>b[T]]=(f[T][tr[p][j]][l+j>b[T]]+f[T-][i][l])%mod;

                if(!j) f[T][tr[p][j]][]=(f[T][tr[p][j]][]+f[T-][i][l])%mod;//前导0

            }

        }

    }

}

int main(){

    freopen("count.in","r",stdin);

    freopen("count.out","w",stdout);

    scanf("%s",a+);n=strlen(a+);

    for(int i=;i<=n;i++) b[n-i+]=a[i]-'';

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        scanf("%s",a+);len=strlen(a+);

        for(int j=;j<=len;j++) c[len-j+]=a[j]-'';

        insert(c);

    }

    AC_mach();

    f[][][]=;

    for(int i=;i<=n;i++) dp(i);

    for(int i=;i<n;i++){

        for(int j=;j<=cnt;j++){

            if(!w[j]){

                ans=(ans+(ll)f[i][j][]+f[i][j][]-f[i][j][])%mod;

            }

        }

    }

    for(int i=;i<=cnt;i++){

        if(!w[i]){

            ans=(ans+(ll)f[n][i][]-f[n][i][])%mod;

        }

    }

    printf("%lld",ans);

    return ;

}