bzoj 1030:[JSOI2007]文本生成器

比较裸的AC自动机+Dp，F[i][j][k]表示第i个节点，走了j步，有无有单词(k)的方案数题。

SPOJ的GEN，是这道的加强版。

const int N = 26, M = 110, Maxn = 7010, Mod = 10007;
struct Node {
	Node *Child[N], *Next;
	int Dat, Id;
	bool Danger;
	Node(int _Dat) : Dat(_Dat) {
		Danger = 0, Next = NULL;
		Rep(i, N) Child[i] = NULL;
	}
} *Root;
int n, m;

inline void Build();
inline void Input() {
	static char Dat[M];
	static int Len;
	scanf("%d%d", &m, &n), getchar();
	Root = new Node(0);
	while(m--) {
		scanf("%s", Dat), Len = strlen(Dat);
		Node *Now = Root;
		Rep(i, Len) {
			int x = Dat[i] - 'A';
			if(Now->Child[x] == NULL) Now->Child[x] = new Node(x);
			Now = Now->Child[x];
		}
		Now->Danger = 1;
	}
	
	Build();
}

int Dp[Maxn][M][2];
inline Node* Find(Node *Now, int C);
inline int Work(Node *Now, int Len, bool Danger) {
	if(Now == NULL) return 0;
	if(!Len) return (int)Danger;
	int &Ret = Dp[Now->Id][Len][Danger];
	if(Ret != -1) return Ret;
	Ret = 0;
	Rep(i, N) {
		Node *V = Find(Now, i);
		Ret += Work(V, Len - 1, Danger | V->Danger);
	}
	return (Ret %= Mod);
}
inline void Solve() {
	clr(Dp, 255);
	printf("%d\n", Work(Root, n, 0));
}

int main() {
	Input();
	Solve();
	return 0;
}

struct State {
	Node *Now, *Father;
	State(Node *_Now, Node *_Father) : Now(_Now), Father(_Father) {}
} ;

inline Node* Find(Node *Now, int C) {
	while(Now != Root && Now->Child[C] == NULL) Now = Now->Next;
	return Now->Child[C] != NULL ? Now->Child[C] : Root;
}
inline void Build() {
	static queue<State> Q;
	while(sz(Q)) Q.pop();
	int tot = 0;
	for(Q.push(State(Root, NULL)); sz(Q); Q.pop()) {
		State T = Q.front();
		T.Now->Id = ++tot;
		
		if(T.Now == Root || T.Father == Root) T.Now->Next = Root;
		else T.Now->Next = Find(T.Father->Next, T.Now->Dat);
		for(Node *tab = T.Now->Next; tab != Root && !(T.Now->Danger); tab = tab->Next)
			T.Now->Danger |= tab->Danger;
		
		Rep(i, N)
			if(T.Now->Child[i] != NULL) Q.push(State(T.Now->Child[i], T.Now));
	}
}