题意 : 给出一些病毒串，问你由ATGC构成的长度为 n 且不包含这些病毒串的个数有多少个
分析 : 这题搞了我真特么久啊，首先你需要知道的前置技能包括 AC自动机、构建Trie图、矩阵快速幂，其中矩阵快速幂和AC自动机可能都熟悉，但是这题为什么和矩阵有关系？Trie图是什么呢？好像只听说过Trie树啊！下面我慢慢展开，首先声明本人水平实在实在有限，理解错误的地方请批评指证，万分感激！
与矩阵的联系( 你可能需要百度.... ) ==> 解决此题就要先了解到如何用矩阵去解决 求从A点到B点刚好经过K步的方案数( 可走重复点 )，在 Matrix67的博客里面就有说，并且HDU 2157就是一道原题，可以尝试去了解并且用快速幂AC它，总之最后的结论就是将整幅图转化为邻接矩阵，然后对矩阵求 k 次幂，最后矩阵的(A, B)点数值就是答案。这一题通过Trie图的转化，最后会变成一个很相似的问题，因此就能用矩阵优化解决。
如何转化？强烈推荐参考==>http://blog.csdn.net/morgan_xww/article/details/7834801
但是！这篇博客虽然解释的很棒，我一开始看完之后还是十分模糊，后来了解到这和普通的AC自动机是有区别的，上述博客当中构建出来的是Trie图，这和AC自动机的区别是啥呢？
何谓AC自动机保存后缀节点跳转？何谓”补边“？我是这么理解的，AC自动机在失配时要通过保存的 Fail 不断跳转来达到下一个合法状态，而Trie图是将所有的跳转信息存起来了，不用繁琐的跳，状态转移直接转即可（理解有误请指出！）先来看看这幅图的“效果”，构建此Trie图就是为了模拟构建长度为 n 的合法串的这个过程，想象一下当前构建到了....A 这样末尾为A的一个串，当前所处状态为 1 、那后面能再添什么字符呢？根据上图的“指示”，我们能够添C吗？显然不行，添C就会到达节点 2 这个不合法的状态，那 A 呢？显然是可以的，增添了A之后并没有转移到其他状态，合法！那G和T呢？当然也是可以的，这样会让状态转化到 0 节点。根据这样的规则，那么 n = 1 且 m = {"ACG"、"C"}的时候答案是 3，模拟一下看看就知道了！那么最后的答案就是从 0 这个初始节点走 K 步到达所有合法节点的方案和、用上面说到的那个矩阵问题里面的解决技巧就可以解决。这个实际上就是构建了一个状态图，每一个节点都拥有向“ATCG"转移的能力，也就是有四条出度，但是普通的AC自动机面对非法节点是无法用 Fail 来进行一步转移的，可能要回溯几步（俗称跳 Fail、找到一个最长前缀的节点和当前节点表示字符串的最长后缀一样、KMP思想），但是我们总是希望状态能够一步被转移，代表从一个状态到另一个状态步数+1，也就是什么意思呢？比如 1 这个节点的 A 出度这条边是不存在的，就需要我们去”补边“，很显然这条边应该是补向当前节点 Fail 节点指向的节点的 A 这条边，由于是自上而下 BFS 序更新，所以能够保证前面所有节点的 A 出边已经被计算出来，那么 1 的 Fail 指向的是 0 ，0 的A出边指向 1 ，所以 1 的 A 出边实际上还是指向自己，其他的也是类似。总的来说就是利用了原来AC自动机中不应该去更新的一些出边根据 Fail 补了上去，以达到方便进行状态转移，代码实现很简单，就是在原AC自动机BFS构建 Fail 指针的代码的时候对于不存在Next[i]的节点将其指向当前节点 Fail 节点指向Next[i]，如果你看过我的AC自动机模板代码，那么会发现代码只是加多了一个语句就能达到这个效果，当然！我们还是需要添加一个标记来标记不合法节点的，值得注意的是，如果当前节点的 Fail 指向的节点是不合法节点的话，那么这个状态转移也是不允许的！
inline void BuildFail(){
Node[].fail = 0;
que.push();
while(!que.empty()){
int top = que.front(); que.pop();
;///如果当前节点的Fail指针指向的节点也是末尾节点，那么这个节点也是不合法的！
; i<Letter; i++){
if(Node[top].Next[i]){
) Node[ Node[top].Next[i] ].fail = ;
else{
int v = Node[top].fail;
){
if(Node[v].Next[i]){
Node[ Node[top].Next[i] ].fail = Node[v].Next[i];
break;
}v = Node[v].fail;
}) Node[ Node[top].Next[i] ].fail = ;
}que.push(Node[top].Next[i]);
}?Node[ Node[top].fail ].Next[i]:;///多了这一句！
}
}
}
根据上述所说，实际上构建 Fail 和 ”补边“的代码还能更简便，如下
//1) 如果son[i]不存在，将它指向 当前结点now的fail指针指
//向结点的i号后继(保证一定已经计算出来)。
//2) 如果son[i]存在，将它的fail指针指向 当前结点now的fail
//指针指向结点的i号后继(保证一定已经计算出来)。
inline void BuildFail(){
Node[].fail = 0;
; i<Letter; i++){
].Next[i]){
Node[Node[].Next[i]].fail = ;
que.push(Node[].Next[i]);
}].Next[i] = ;///必定指向根节点
}
while(!que.empty()){
int top = que.front(); que.pop();
;
; i<Letter; i++){
int &v = Node[top].Next[i];
if(v){
que.push(v);
Node[v].fail = Node[Node[top].fail].Next[i];
}else v = Node[Node[top].fail].Next[i];
}
}
}
那么只要我们绘出了这副 Trie 图，我们就能知道各个点到其他点只通过一步的方案数，最后存到矩阵去进行 n 次快速幂，最后累加从 0 到其他合法点的答案即可
如果不懂！没关系，那些都是我参考了很多东西得出来的口胡，可以看看原文，以上参考 ==>
http://www.doc88.com/p-9913363530128.html( AC自动机 与 Trie图 )
blog.csdn.net/mobius_strip/article/details/22549517 ( 大牛的总结 )
http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html ( AC自动机 与 Trie 图 )
最后AC代码(96ms) 提醒 : 如果TLE了，那么矩阵快速幂的过程中加完一行再模，不要边加边模
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
;
;
const int MOD = 1e5;
int maxn;
];
][]; }unit, M;
mat operator * (mat a, mat b)
{
mat ret;
long long x;
; i<maxn; i++){
; j<maxn; j++){
x = ;
; k<maxn; k++){
x += (long long)a.m[i][k]*b.m[k][j];
}
ret.m[i][j] = x % MOD;
}
}
return ret;
}
inline ; i<maxn; i++) unit.m[i][i] = ; }
mat pow_mat(mat a, int n)
{
mat ret = unit;
while(n){
) ret = ret * a;
a = a*a;
n >>= ;
}
return ret;
}
struct Aho{
struct StateTable{
int Next[Letter];
int fail, flag;
}Node[Max_Tot];
int Size;
queue<int> que;
inline void init(){
while(!que.empty()) que.pop();
memset(Node[].Next, , ].Next));
Node[].fail = Node[].flag = ;
Size = ;
}
inline void insert(char *s){
;
; s[i]; i++){
int idx = mp[s[i]];
if(!Node[now].Next[idx]){
memset(Node[Size].Next, , sizeof(Node[Size].Next));
Node[Size].fail = Node[Size].flag = ;
Node[now].Next[idx] = Size++;
}
now = Node[now].Next[idx];
}
Node[now].flag = ;
}
inline void BuildFail(){
Node[].fail = 0;
que.push();
while(!que.empty()){
int top = que.front(); que.pop();
;///如果当前节点的Fail指针指向的节点也是末尾节点，那么这个节点也是不合法的！
; i<Letter; i++){
if(Node[top].Next[i]){
) Node[ Node[top].Next[i] ].fail = ;
else{
int v = Node[top].fail;
){
if(Node[v].Next[i]){
Node[ Node[top].Next[i] ].fail = Node[v].Next[i];
break;
}v = Node[v].fail;
}) Node[ Node[top].Next[i] ].fail = ;
}que.push(Node[top].Next[i]);
}?Node[ Node[top].fail ].Next[i]:;///多了这一句！
}
}
}
////1) 如果son[i]不存在，将它指向 当前结点now的fail指针指
////向结点的i号后继(保证一定已经计算出来)。
//
////2) 如果son[i]存在，将它的fail指针指向 当前结点now的fail
////指针指向结点的i号后继(保证一定已经计算出来)。
// inline void BuildFail(){
// Node[0].fail = 0;
// for(int i=0; i<Letter; i++){
// if(Node[0].Next[i]){
// Node[Node[0].Next[i]].fail = 0;
// que.push(Node[0].Next[i]);
// }else Node[0].Next[i] = 0;///必定指向根节点
// }
// while(!que.empty()){
// int top = que.front(); que.pop();
// if(Node[Node[top].fail].flag) Node[top].flag = 1;
// for(int i=0; i<Letter; i++){
// int &v = Node[top].Next[i];
// if(v){
// que.push(v);
// Node[v].fail = Node[Node[top].fail].Next[i];
// }else v = Node[Node[top].fail].Next[i];
// }
// }
// }
inline void BuildMatrix(){
; i<Size; i++)
; j<Size; j++)
M.m[i][j] = ;
; i<Size; i++){
; j<Letter; j++){
if(!Node[i].flag && !Node[ Node[i].Next[j] ].flag)
M.m[i][Node[i].Next[j]]++;
}
}
maxn = Size;
}
}ac;
];
int main(void)
{
mp[,
mp[,
mp[,
mp[;
int n, m;
while(~scanf("%d %d", &m, &n)){
ac.init();
; i<m; i++){
scanf("%s", S);
ac.insert(S);
}
ac.BuildFail();
ac.BuildMatrix();
// for(int i=0; i<10; i++){
// for(int j=0; j<10; j++){
// printf("%d ", M.m[i][j]);
// }puts("");
// }puts("");
init_unit();
M = pow_mat(M, n);
// for(int i=0; i<10; i++){
// for(int j=0; j<10; j++){
// printf("%d ", M.m[i][j]);
// }puts("");
// }puts("");
;
; i<ac.Size; i++)
ans += M.m[][i];
ans %= MOD;
printf("%d\n", ans);
}
;
}
瞎想 : AC自动机上的DP真的好难啊！！！