[bzoj3530][Sdoi2014]숫자[AC자동기][디지털 DP]

[제목 링크]https://www.lydsy.com/JudgeOnline/problem.php?id=3530[문제풀이] 모든 숫자열 S를 AC자동기로 만들고 자동기에 DP를 넣으면 됩니다. 숫자열에 전도 0이 있을 수 있지만 당신의 수는 안 됩니다.시간 복잡도 O(l∗L∗10)O(l∗L∗10)[코드]

# include 
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    N       2010
using namespace std;
int read(){
    int tmp = 0, fh = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9'){tmp = tmp * 10 + ch - '0'; ch = getchar(); }
    return tmp * fh;
}
struct Node{
    int son[10], tag;
}T[N];
int nex[N], f[N][N][2][2], q[N], n, m, place;
char s[N], tmp[N];
const int P = 1e9 + 7;
void extend(char *tmp, int l){
    int p = 0;
    for (int i = 1; i <= l; i++){
        if (T[p].son[tmp[i] - '0'] == 0)
            T[p].son[tmp[i] - '0'] = ++place;
        p = T[p].son[tmp[i] - '0'];
    }
    T[p].tag = true;
}
void buildfail(){
    int pl = 1, pr = 1; q[1] = 0;
    while (pl <= pr){
        int x = q[pl++];
        for (int i = 0; i <= 9; i++)
            if (T[x].son[i] != 0){
                int p = x;
                while (p != 0 && T[nex[p]].son[i] == 0) 
                    p = nex[p];
                if (x == 0) nex[T[x].son[i]] = 0;
                    else {
                        nex[T[x].son[i]] = T[nex[p]].son[i];
                        if (T[T[nex[p]].son[i]].tag == true)
                            T[T[x].son[i]].tag = true;
                    }
                q[++pr] = T[x].son[i];
            }
    }
}
int solve(){
    for (int i = 0; i <= n - 1; i++){
        for (int j = 0; j <= place; j++){
            if (T[j].tag) continue;
            for (int k = 1; k <= 9; k++){
                int p = j;
                while (p != 0 && T[p].son[k] == 0) p = nex[p];
                p = T[p].son[k];
                if (T[p].tag) continue;
                if (s[i + 1] > k)
                    f[i + 1][p][1][0] = (1ll * f[i + 1][p][1][0] + f[i][j][0][0] + f[i][j][0][1]) % P;
                if (s[i + 1] == k){
                    f[i + 1][p][1][0] = (f[i + 1][p][1][0] + f[i][j][0][0]) % P;
                    f[i + 1][p][1][1] = (f[i + 1][p][1][1] + f[i][j][0][1]) % P;        
                }
                if (s[i + 1] < k)
                    f[i + 1][p][1][0] = (f[i + 1][p][1][0] + f[i][j][0][0]) % P;
            }
            if (s[i + 1] > 0)
                f[i + 1][0][0][0] = f[i][0][0][0] + f[i][0][0][1];
                else {
                    f[i + 1][0][0][1] = f[i][0][0][1];
                    f[i + 1][0][0][0] = f[i][0][0][0];
                }
            for (int k = 0; k <= 9; k++){
                int p = j;
                while (p != 0 && T[p].son[k] == 0) p = nex[p];
                p = T[p].son[k];
                if (T[p].tag) continue;
                if (s[i + 1] > k)
                    f[i + 1][p][1][0] = (1ll * f[i + 1][p][1][0] + f[i][j][1][0] + f[i][j][1][1]) % P;
                if (s[i + 1] == k){
                    f[i + 1][p][1][0] = (f[i + 1][p][1][0] + f[i][j][1][0]) % P;
                    f[i + 1][p][1][1] = (f[i + 1][p][1][1] + f[i][j][1][1]) % P;        
                }
                if (s[i + 1] < k)
                    f[i + 1][p][1][0] = (f[i + 1][p][1][0] + f[i][j][1][0]) % P;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= place; i++)
        if (!T[i].tag)
            ans = (1ll * ans + f[n][i][1][0] + f[n][i][1][1]) % P;
    return ans;
}
int main(){
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    scanf("
%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
        s[i] = s[i] - '0';
    m = read();
    for (int i = 1; i <= m; i++){
        scanf("
%s", tmp + 1);
        int l = strlen(tmp + 1);
        extend(tmp, l);
    }
    buildfail();
    f[0][0][0][1] = 1;
    printf("%d
", solve());
    return 0;
}