HDU 2243 考研路茫茫——单词情结

Problem Description

背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele 也终于要开始背单词了。
一天，Lele 在某本单词书上看到了一个根据词根来背单词的方法。比如 $“ab”$,放在单词前一般表示“相反，变坏，离去"等。

于是Lele想，如果背了 $n$ 个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过 $l$，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。

比如一共有 $2$ 个词根 $“aa”$ 和 $“ab”$ ，则可能存在 $104$ 个长度不超过 $3$ 的单词，分别为

• (2个) $aa,ab$
• (26个)$aaa,aab,aac\cdots aaz$
• (26个)$aba,abb,abc\cdots abz$
• (25个)$baa,caa,daa\cdots zaa$
• (25个)$bab,cab,dab\cdots zab$

这个只是很小的情况。而对于其他复杂点的情况，Lele 实在是数不出来了，现在就请你帮帮他。

Input

本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数 $n$ 和 $l$（$0<n<6$, $0<l<2^{31}$）。
第二行有 $n$ 个词根，每个词根仅由小写字母组成，长度不超过 $5$。两个词根中间用一个空格分隔开。

Output

对于每组数据，请在一行里输出一共可能的单词数目。

由于结果可能非常巨大，你只需要输出单词总数模 $2^{64}$ 的值。

Sample Input

2 3
aa ab
1 2
a

Idea

我们可以依据容斥原理，长度不超过 $l$ 的所有小写字母组成的串有 $\sum\limits_{i=1}^l 26^i$ 个；若能求出不包含任何一个词根的串的个数 $t$，则答案为 $\sum\limits_{i=1}^l26^i-t$。

类似 POJ 2778 DNA Sequence，我们构建AC自动机；自动机上将一切词根禁止，那么在自动机上游走 $k$（$1\le k\le l$）步的方案数就是不包含任何词根的串的个数 $t$。自动机的邻接矩阵为 $A$，在AC自动机上游走 $k$ 步，$\sum\limits_{i=0}^{tot}A_{0,i}^k$ 即为答案，$tot$ 为AC自动机上最大点的编号，树根编号为 $0$。要构造长度不超过 $l$ 的串，总方案数 $t=\sum\limits_{k=1}^l\sum\limits_{i=0}^{tot}A_{0,i}^k=\sum\limits_{i=0}^{tot}\left(\sum\limits_{k=1}^lA^k\right)_{0,i}$。

由于数据量大，答案需要模 $2^{64}$，可以直接用 $\text{unsigned long long}$ 自然溢出。对于等比数列求和 $\sum\limits_{i=1}^{l}26^i$，直接利用求和公式需要求 $25$ 模 $2^{64}$ 意义下的逆元，好麻烦，还得扩展欧几里得；对于等比矩阵求和 $\sum\limits_{k=1}^l A^k$，利用求和公式还需要求逆矩阵，麻烦死了，还要高斯消元，增加复杂度。因此不妨直接递归求等比数列、矩阵的和。

令 $S_n=a+a^2+\cdots+a^n$。

若 $n$ 为偶数，则

$$S_n=(a+a^2+\cdots+a^{\frac{n}{2}})+a^{\frac{n}{2}}(a+a^2+\cdots+a^{\frac{n}{2}})=(1+a^{\frac{n}{2}})S_{\frac{n}{2}}$$

若 $n$ 为奇数，则

$$S_n=(a+a^2+\cdots+a^{\frac{n-1}{2}})+a^{\frac{n-1}{2}}(a+a^2+\cdots+a^{\frac{n-1}{2}})+a^n=(1+a^{\frac{n-1}{2}})S_{\frac{n-1}{2}}+a^n$$

Code

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
typedef unsigned long long ull;
const int CHARACTER_SET_SIZE = 26;
const int MAX_N = 7;
const int MAX_L = 6;
int n, l;
int trie[MAX_N * MAX_L][CHARACTER_SET_SIZE], tot;
bool permitted[MAX_N * MAX_L];
int fail[MAX_N * MAX_L];
char str[MAX_L];
struct Matrix {
	ull m[MAX_N * MAX_L][MAX_N * MAX_L];
	Matrix() {
		memset(m, 0, sizeof(m));
	}
};
inline void init();
void insert(char s[]);
void buildACAutomaton();
Matrix operator*(const Matrix& x, const Matrix& y);
Matrix operator+(const Matrix& x, const Matrix& y);
Matrix quickPow(Matrix a, int b);
ull quickPow(ull a, int b);
ull isometricSeriesSum(ull a, int n);
Matrix isometricSeriesSum(Matrix a, int n);
Matrix initialMatrix();
int main() {
	while (~scanf("%d%d", &n, &l)) {
		init();
		for (int i = 1; i <= n; i++) {
			scanf("%s", str);
			insert(str);
		}
		buildACAutomaton();
		Matrix finalMatrix = isometricSeriesSum(initialMatrix(), l);
		ull ans = 0;
		for (int i = 0; i <= tot; i++) {
			ans += finalMatrix.m[0][i];
		}
		ull totol = isometricSeriesSum(26, l);
		ans = totol - ans;
		printf("%llu\n", ans);
	}
}
inline void init() {
	memset(trie, 0, sizeof(trie));
	memset(fail, 0, sizeof(fail));
	tot = 0;
	memset(permitted, true, sizeof(permitted));
}
void insert(char s[]) {
	int len = strlen(s), p = 0;
	for (int i = 0; i < len; i++) {
		int ch = s[i] - 'a';
		if (!trie[p][ch]) {
			trie[p][ch] = ++tot;
		}
		p = trie[p][ch];
	}
	permitted[p] = false;
}
void buildACAutomaton() {
	queue<int>q;
	for (int i = 0; i < CHARACTER_SET_SIZE; i++) {
		if (trie[0][i]) {
			q.push(trie[0][i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		//---------------------------------------------
		//If the suffix of a string is not allowed
		//then the string is not allowed
		//---------------------------------------------
		if (!permitted[fail[u]]) {
			permitted[u] = false;
		}
		for (int i = 0; i < CHARACTER_SET_SIZE; i++) {
			if (trie[u][i]) {
				fail[trie[u][i]] = trie[fail[u]][i];
				q.push(trie[u][i]);
			} else {
				trie[u][i] = trie[fail[u]][i];
			}
		}
	}
}
Matrix operator*(const Matrix& x, const Matrix& y) {
	Matrix res;
	for (int i = 0; i <= tot; i++) {
		for (int j = 0; j <= tot; j++) {
			for (int k = 0; k <= tot; k++) {
				res.m[i][j] += x.m[i][k] * y.m[k][j];
			}
		}
	}
	return res;
}
Matrix operator+(const Matrix& x, const Matrix& y) {
	Matrix res;
	for (int i = 0; i <= tot; i++) {
		for (int j = 0; j <= tot; j++) {
			res.m[i][j] = x.m[i][j] + y.m[i][j];
		}
	}
	return res;
}
Matrix quickPow(Matrix a, int b) {
	Matrix res;
	//to construc an identity matrix
	for (int i = 0; i <= tot; i++) {
		res.m[i][i] = 1;
	}
	while (b) {
		if (b & 1) {
			res = res * a;
		}
		a = a * a;
		b >>= 1;
	}
	return res;
}
ull quickPow(ull a, int b) {
	ull res = 1;
	while (b) {
		if (b & 1) {
			res = res * a;
		}
		a = a * a;
		b >>= 1;
	}
	return res;
}
ull isometricSeriesSum(ull a, int n) {
	if (n == 1) {
		return a;
	}
	ull res = 1;
	res = res + quickPow(a, n >> 1);
	res = res * isometricSeriesSum(a, n >> 1);
	if (n & 1) {
		res = res + quickPow(a, n);
	}
	return res;
}
Matrix isometricSeriesSum(Matrix a, int n) {
	if (n == 1) {
		return a;
	}
	Matrix res;
	for (int i = 0; i <= tot; i++) {
		res.m[i][i] = 1;
	}
	res = res + quickPow(a, n >> 1);
	res = res * isometricSeriesSum(a, n >> 1);
	if (n & 1) {
		res = res + quickPow(a, n);
	}
	return res;
}
Matrix initialMatrix() {
	Matrix res;
	for (int i = 0; i <= tot; i++) {
		//the node i isn't permitted to reach
		if (!permitted[i]) {
			continue;
		}
		for (int j = 0; j < CHARACTER_SET_SIZE; j++) {
			//one of the sons of node i isn't permitted to reach
			if (!permitted[trie[i][j]]) {
				continue;
			}
			++res.m[i][trie[i][j]];
		}
	}
	return res;
}