http://poj.org/problem?id=2778 有空再重新做下，对状态图的理解很重要 题解： http://blog.csdn.net/morgan_xww/article/details/7834801 另外做了矩阵幂的模板： //ac.sz是矩阵的大小void mulmtr(long long x[MAXNODE][MAXNODE],long long y[M

// poj 2778 AC自动机 + 矩阵快速幂//// 题目链接：// // http://poj.org/problem?id=2778//// 解题思路：//// 建立AC自动机,确定状态之间的关系,构造出,走一步// 能到达的状态矩阵,然后进行n次乘法,就可以得到状态间// 走n步的方法数.// 精髓:// 1):这个ac自动机有一些特别,根节点是为空串,

题意：有m种DNA序列是有疾病的，问有多少种长度为n的DNA序列不包含任何一种有疾病的DNA序列。（仅含A,T,C,G四个字符） 首先我们需要知道 给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值 把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点