POJ 2778 DNA Sequence（AC自动机+矩阵快速幂）

题意：有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 ;

 }

巴特西

POJ 2778 DNA Sequence（AC自动机+矩阵快速幂）

最新文章

热门文章