题目链接：http://poj.org/problem?id=2778
题意：有m种DNA序列是有疾病的，问有多少种长度为n的DNA序列不包含任何一种有疾病的DNA序列。（仅含A,T,C,G四个字符）
思路：Trie图的状态转移，用矩阵mat[i][j]来表示从结点i到j只走一步有几种走法，那么mat的n次幂就表示从结点i到j走n步有几种走法，题目要求解的就是从头节点走n步且不包含危险结点的走法。
mat = mat^n ans = (mat[0][0] + mat[0][1] + ... + mat[0][num]) num为结点个数
code：
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
const int KIND = ;
const int MAXN = ;
const int MOD = ;
typedef long long LL; struct Trie
{
int next[MAXN][KIND], fail[MAXN];
bool isExit[MAXN];
int root, L;
map<char, int> mp;
LL mat[MAXN][MAXN];
LL ret[MAXN][MAXN];
LL tmp[MAXN][MAXN];
int create()
{
for (int i = ; i < KIND; ++i)
next[L][i] = -;
isExit[L++] = false;
return L - ;
}
void init()
{
L = ;
root = create();
mp['A'] = ;
mp['C'] = ;
mp['G'] = ;
mp['T'] = ;
memset(mat, , sizeof(mat));
memset(ret, , sizeof(ret));
}
void insert(char str[])
{
int now = root;
int len = strlen(str);
for (int i = ; i < len; ++i)
{
if (- == next[now][mp[str[i]]])
next[now][mp[str[i]]] = create();
now = next[now][mp[str[i]]];
}
isExit[now] = true;
}
void build()
{
queue<int>Q;
for (int i = ; i < KIND; ++i)
{
if (- == next[root][i])
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
}
while (!Q.empty())
{
int now = Q.front();
Q.pop();
if (isExit[fail[now]])
isExit[now] = true;
for (int i = ; i < KIND; ++i)
{
if (- == next[now][i])
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
void getMatrix()
{
for (int i = ; i < L; ++i)
{
for (int j = ; j < KIND; ++j)
{
if (!isExit[next[i][j]])
++mat[i][next[i][j]];
}
}
}
void matrixMul(LL mat1[MAXN][MAXN], LL mat2[MAXN][MAXN])
{
LL mat3[MAXN][MAXN];
for (int i = ; i < L; ++i)
{
for (int j = ; j < L; ++j)
{
mat3[i][j] = ;
for (int k = ; k < L; ++k)
mat3[i][j] = (mat3[i][j] + mat1[i][k] * mat2[k][j]) % MOD;
}
}
memcpy(mat1, mat3, sizeof(mat3));
}
void matrixQuickMod(LL n)
{
getMatrix();
for (int i = ; i < L; ++i)
{
ret[i][i] = ;
for (int j = ; j < L; ++j)
tmp[i][j] = mat[i][j];
}
while (n)
{
if (n & ) matrixMul(ret, tmp);
matrixMul(tmp, tmp);
n >>= ;
}
}
};
Trie ac;
char str[];
int main()
{
int m;
LL n;
while (scanf("%d %lld", &m, &n) != EOF)
{
ac.init();
for (int i = ; i < m; ++i)
{
scanf("%s", str);
ac.insert(str);
}
ac.build();
ac.matrixQuickMod(n);
int ans = ;
for (int i = ; i < ac.L; ++i)
ans = (ans + ac.ret[][i]) % MOD;
printf("%d\n", ans);
}
return ;
}