【BZOJ 1030】【JSOI 2007】文本生成器 AC自动机+递推

一直不理解到底怎么做啊，想了好久$TwT$

最后终于明白了为什么找到第一个满足条件的$fail$就计算，因为避免重复，这个回答，，，

然后$root$下面要接上26个节点，这里26个字母中不在字典内的都用$f[i][0]$代替了，这个也想了好久，$==$我还是回家种地吧。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mo 10007

#define N 103

#define M 6003

using namespace std;

int q[M], c[M][26], w[M], fail[M], f[N][M], n, m, cnt = 0;

inline void ins(char *s) {

	int len = strlen(s), now = 0;

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

		int t = s[i] - 'A';

		if (!c[now][t])

			c[now][t] = ++cnt;

		now = c[now][t];

	}

	w[now] = 1;

}

inline void BFS() {

	int head = 0, tail = 1, now = 0;

	q[1] = 0;

	while (head != tail) {

		now = q[++head];

		for(int t = 0; t < 26; ++t)

			if (c[now][t]) {

				q[++tail] = c[now][t];

				if (now == 0) continue;

				int tmp = fail[now];

				while (tmp && !c[tmp][t])

					tmp = fail[tmp];

				fail[c[now][t]] = c[tmp][t];

				if (w[c[tmp][t]])

					w[c[now][t]] = 1; //!!!!!!!

			}

	}

}

inline int ipow(int x, int nn) {

	int ans = 1;

	for(int t = x; nn; nn >>= 1, t = (t * t) % mo)

		if (nn & 1) {

			ans = (ans * t);

			if (ans >= mo)

				ans = ans % mo;

		}

	return ans;

}

inline void AC() {

	f[0][0] = 1;

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

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

			if (f[i][j]) {

				for(int t = 0; t < 26; ++t) {

					int tmp = j;

					while (tmp && !c[tmp][t])

						tmp = fail[tmp];

					tmp = c[tmp][t];

					if (!w[tmp]) {

						f[i + 1][tmp] += f[i][j];

						if (f[i + 1][tmp] >= mo)

							f[i + 1][tmp] %= mo;

					}

				}

			}

	int _ = 0, al = ipow(26, m);

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

		if (!w[i]) {

			_ += f[m][i];

			if (_ > mo)

				_ %= mo;

		}

	int ans = ((al - _) % mo + mo) %mo;

	printf("%d\n", ans);

}

int main() {

	scanf("%d%d", &n, &m);

	char s[N];

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

		scanf("%s", s), ins(s);

	BFS();

	AC();

	return 0;

}

最后终于做出来了，因为看了别人的模板，，，，这，，，