ZOJ 3494 BCD Code AC自動機 + 數位DP

題目大意：

就是現在有0~9對應的BCD碼(就是對應的4位的二進制), 然後給出了n串(0 <= n <= 1000)不能出現的串(隻包含0和1)， 現在問在數字A到B之間有多少個數在轉換成BCD碼表示之後不包含這n個串，1 <= A <= B <= 10^200

大緻思路：

首先考慮到A和B的範圍，暴力是不可行的，這裡需要用到數位DP，也就是逐位确定的思想，首先用AC自動機算出從狀态i出發下一位是0~9分别可到達的狀态，或者不可走，然後逐位确定各個數位的值即可，記憶化搜尋提高效率，啟示這個數位DP還是挺簡單的，注意前導零的問題即可。

代碼如下：

Result  :  Accepted     Memory  :  3676 KB     Time  :  210 ms

/*
 * Author: Gatevin
 * Created Time:  2014/11/27 10:18:15
 * File Name: Kagome.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

const lint mod = 1000000009LL;
int n;
char num[210];
int bit[210];

int bcd[2010][10];
//bcd[i][j]表示從AC自動機的i狀态，下一個數字是j會到達的狀态，為-1表示不可走

lint dp[2010][210];
//dp[i][j]表示從AC自動機的i狀态，接下來的j位沒有邊界和前導零限制時的方案數，用于記憶化

struct Trie
{
    int next[2010][2], fail[2010];
    bool end[2010];
    int L, root;
    int newnode()
    {
        for(int i = 0; i < 2; i++)
            next[L][i] = -1;
        end[L++] = 0;
        return L - 1;
    }
    void init()
    {
        L = 0;
        root = newnode();
        return;
    }
    void insert(char *s)
    {
        int now = root;
        for(; *s; s++)
        {
            if(next[now][*s - '0'] == -1)
                next[now][*s - '0'] = newnode();
            now = next[now][*s - '0'];
        }
        end[now] = 1;
        return;
    }
    void build()
    {
        queue <int> Q;
        fail[root] = root;
        Q.push(root);
        while(!Q.empty())
        {
            int now = Q.front();
            Q.pop();
            if(end[fail[now]]) end[now] = 1;//标記所有不能到達的點
            for(int i = 0; i < 2; i++)
                if(next[now][i] == -1)
                    next[now][i] = now == root ? root : next[fail[now]][i];
                else
                {
                    fail[next[now][i]] = now == root ? root : next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }
        return;
    }
};

Trie AC;

void BCD()//計算bcd數組
{
    for(int i = 0; i < AC.L; i++)
        for(int j = 0; j < 10; j++)
        {
            bcd[i][j] = i;
            if(AC.end[bcd[i][j]])
            {
                bcd[i][j] = -1;
                continue;
            }
            for(int k = 3; k >= 0; k--)
            {
                if(j & (1 << k))
                    bcd[i][j] = AC.next[bcd[i][j]][1];
                else
                    bcd[i][j] = AC.next[bcd[i][j]][0];
                if(AC.end[bcd[i][j]])
                {
                    bcd[i][j] = -1;
                    break;
                }
            }
        }
    return;
}

/*
 * 傳回剩下的長度為L需要填充，目前在AC自動機的pos狀态，
 * bound表示接下來這一位是否考慮上界bit限制
 * lead表示之前是否已經有數字，即目前位填0是否有狀态轉移(前導零不轉移)
 */
lint dfs(int L, int pos, bool bound, bool lead)//寫的不怎麼優美....
{
    if(L == 0 && lead) return 1;
    if(L == 0 && !lead) return 0;
    if(dp[pos][L] != -1 && !bound && lead) return dp[pos][L];
    lint ret = 0;
    if(!lead)//沒有前導零
    {
        ret = (ret + dfs(L - 1, pos, false, false)) % mod;//繼續沒有前導零
            if(bound)//有上界限制
            {
                for(int i = 1; i < bit[L]; i++)//接下來填的數比目前位小，接下去就沒有限制
                    if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
                if(bcd[pos][bit[L]] != -1) ret = (ret + dfs(L - 1, bcd[pos][bit[L]], true, true)) % mod;//有限制
            }
            else
                for(int i = 1; i < 10; i++)//沒有限制就随便填了，接下去也沒有限制
                    if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
    }
    else
    {
        if(bound)
        {
            for(int i = 0; i < bit[L]; i++)
                if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
            if(bcd[pos][bit[L]] != -1) ret = (ret + dfs(L - 1, bcd[pos][bit[L]], true, true)) % mod;
        }
        else
            for(int i = 0; i < 10; i++)
                if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
    }
    if(lead && dp[pos][L] == -1 && !bound) dp[pos][L] = ret;//記憶化
    return ret;
}


//計算從0到目前數字有多少是不包含那N個危險串的
lint solve(int len)
{
    if(len == 0) return 0;
    for(int i = 0; i < len; i++)
        bit[len - i] = num[i] - '0';
    return dfs(len, AC.root, true, false);
}

int main()
{
    int t;
    char ts[22];
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        AC.init();
        while(n--)
        {
            scanf("%s", ts);
            AC.insert(ts);
        }
        AC.build();
        BCD();
        scanf("%s", num);
        int len = strlen(num);
        /*
         * 将目前的左界減去1
         */
        if(num[len - 1] > '0')
        {
            int tmp = len - 1;
            if(len == 1 && num[len - 1] == '1') len = 0;
            num[tmp] = num[tmp] - 1;
        }
        else
        {
            num[len - 1] = '9';
            int now = len - 2;
            while(num[now] == '0')
            {
                num[now] = '9';
                now--;
            }
            if(num[now] == '1' && now == 0)
            {
                for(int i = 0; i < len; i++)
                    num[i] = num[i + 1];
                len--;
            }
            else
                num[now] = num[now] - 1;
        }
        memset(dp, -1, sizeof(dp));
        lint A = solve(len);
        scanf("%s", num);
        len = strlen(num);
        lint B = solve(len);
        printf("%lld\n", (B - A + mod) % mod);
    }
    return 0;
}