当前位置: 代码迷 >> 综合 >> AC自动机+矩阵快速幂 POJ 2778
  详细解决方案

AC自动机+矩阵快速幂 POJ 2778

热度:64   发布时间:2024-01-04 09:15:20.0

题意:有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到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要求出A^k即可。