題目大意: 問A到B之間的所有整數，轉換成BCD Code後，有多少個不包含屬於給定病毒串集合的子串,A,B <=10^200,病毒串總長度<= 2000.
解題思路: 因為時間問題，這是我這次復習AC自動機的最後一題了。ac自動機A的很爽，可是其他方面太弱逼，無可奈何必須去復習其他方面了。
看完題目就給出題者跪了，看似毫不相關但實則有聯系的的兩個東西被結合起來，真是神來之筆。AC自動機上明顯的狀態使得我們很容易在AC自動機上進行DP，而數位DP又是DP裡面一類比較典型的DP，之前我一直認為數位DP應該是利用數字直接一位一位的構造就可以，這題利用自動機構造出一個數字與其他數字間能否相互到達的矩陣，然後利用這個矩陣進行數位DP。這樣一分析，似乎並不是毫無相關。
以終為始，我們先分析下最後的數位dp為什麼需要用到自動機。如果一個數不含病毒串，那麼這個數中的所有數字編成BCD碼並且連接起來後就必須不包含病毒串。普通的數位DP構造的兩個相鄰數字沒什麼約束，而這題的約束有兩個，一是數字本身編成BCD碼後可能含有病毒串，二是兩個數字連起來後他們的BCD碼也連起來了，這時可能含有病毒串，一是二的特例。這樣問題就轉變成了我們構造若干個串，使得這些串不包含病毒串。問題一轉變就和AC自動機扯上關系了，我們用這個串去ac自動機上跑一跑就知道含不含病毒串了。
我們需要將自動機上的狀態壓縮成一個mat[MAXSIZE][10]矩陣，mat[i][j]表示位置i走過j編成的BCD碼即四位二進制數後到達的位置，如果沒辦法到達設為-1.接著我們利用mat進行數位DP，mat[i][j]中的i表示位置，但除root外它也表示數字，i->next[k] = ii，這裡的ii就表示k。
用dp[pos][ac][limit][zero]來表示狀態，pos表示數字的第幾位，ac為ac自動機上的位置，limit=0表示沒有上限，limit=1表示上限為digit[pos],zero為0表示非前導0，此時需要判斷mat[ac][k]是否為-1，為-1說明沒辦法構造下一個數字k，否則可以構造，當zero為1表示是前導0，如果下一個是0那麼表示這些都是無用的0，轉移到下一個位置都應該是root，不是0的話就需要判斷mat[0][k]了。
狀態明確了以後用記憶化搜索很好寫。
測試數據：
Input:
10
0
1 10
1
00
1 10
1
00
1 100
1
1111
1 100
2
01
10
1 100
Output:
10
3
9
98
0
代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXNODE 2
#define MAXSIZE 2100
#define MOD 1000000009
int n,m;
int ans;
char str[MAXSIZE];
char A[MAXSIZE],B[MAXSIZE];
struct ACnode {
int flag,in;
ACnode *next[MAXNODE],*fail,*father;
};
struct AC_Auto {
int head,tail,total;
int digit[210];
int ans,dp[210][MAXSIZE][2][2];
int next[MAXSIZE][10];
ACnode *root,*p,*q;
ACnode *qu[MAXSIZE],tree[MAXSIZE];
void Initial() {
total = 0;
head = tail = 0;
root = CreateNode();
root->fail = root;
}
ACnode *CreateNode() {
tree[total].flag = 0;
tree[total].in = total;
tree[total].next[0] = NULL;
tree[total].next[1] = NULL;
return &tree[total++];
}
int GetHash(char c) {
return c - '0';
}
void Insert(char *str) {
p = root;
for (int i = 0; str[i]; ++i) {
int k = GetHash(str[i]);
if (p->next[k] == NULL)
p->next[k] = CreateNode();
p = p->next[k];
}
p->flag = 1;
}
void Build_AC() {
qu[head++] = root;
while (tail < head) {
p = qu[tail++];
for (int k = 0; k < MAXNODE; ++k)
if (p->next[k]) {
if (p == root) p->next[k]->fail = root;
else p->next[k]->fail = p->fail->next[k];
p->next[k]->flag |= p->next[k]->fail->flag;
qu[head++] = p->next[k];
}
else {
if (p == root) p->next[k] = root;
else p->next[k] = p->fail->next[k];
}
}
}
int Next(int pos,int num) {
if (tree[pos].flag == 1) return -1;
int realpos = pos;
for (int i = 3; i >= 0; --i) {
int k = ((num >> i) & 1);
if (tree[realpos].next[k]->flag != 1)
realpos = tree[realpos].next[k]->in;
else return -1;
}
return realpos;
}
void Cal_Next() {
for (int i = 0; i < total; ++i)
for (int j = 0; j <= 9; ++j)
next[i][j] = Next(i,j);
}
int Dfs(int pos,int ac,int limit,int zero) {
if (pos == -1) return 1;
if (dp[pos][ac][limit][zero] != -1)
return dp[pos][ac][limit][zero];
int sum = 0;
int tl,tz,end = limit ? digit[pos] : 9;
for (int i = 0; i <= end; ++i) {
tz = zero && i == 0;
tl = limit && (i == end);
if (tz == 1) {
sum = sum + Dfs(pos-1,0,tl,tz);
if (sum >= MOD) sum -= MOD;
continue;
}
if (next[ac][i] == -1) continue;
sum = sum + Dfs(pos-1,next[ac][i],tl,tz);
if (sum >= MOD) sum -= MOD;
}
dp[pos][ac][limit][zero] = sum;
return dp[pos][ac][limit][zero];
}
int Cal(char *num) {
int pos;
memset(dp,-1,sizeof(dp));
reverse(num,num+strlen(num));
for (pos = 0; num[pos]; ++pos)
digit[pos] = num[pos] - '0';
return Dfs(pos-1,0,1,1);
}
void Debug() {
for (int i = 0; i < total; ++i)
for (int j = 0; j <= 9; ++j)
printf("i = %d j = %d next = %d\n",i,j,next[i][j]);
}
}AC;
void Subtoone(char *A) {
int len = strlen(A),i = len -1;
if (A[i] == 0) {
A[i] = '9';
while (A[i] == '0') i--;
}
A[i] = A[i] - '0' - 1 + '0';
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
AC.Initial();
for (i = 1; i <= n; ++i) {
scanf("%s",str);
AC.Insert(str);
}
ans = 0;
AC.Build_AC();
AC.Cal_Next();
//AC.Debug();
scanf("%s",A);
Subtoone(A);
ans = ans - AC.Cal(A);
if (ans < 0) ans += MOD;
scanf("%s",B);
ans = ans + AC.Cal(B);
if (ans >= MOD) ans -= MOD;
printf("%d\n",ans);
}
}
