DNA Sequence

题目：

http://poj.org/problem?id=2778

https://www.acwing.com/problem/content/4750/

推荐题解：

https://blog.csdn.net/weixin_39453270/article/details/82013631

标签：AC自动机|DP|矩阵快速幂

将AC自动机建图，并用矩阵快速幂计算状态转移。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using LL = long long;
using std::cin, std::cout;

const int N = 110, MOD = 1e5;

struct TrieNode
{
    int S[4];
    bool end;
    int fail;
} T[N];
int idx;

int getS(char c)
{
    switch (c)
    {
    case 'A': return 0;
    case 'C': return 1;
    case 'T': return 2;
    case 'G': return 3;
    }
    return -1;
}

char S[N];

void ins()
{
    int p = 0;
    for (int i = 0; S[i]; i++)
    {
        int u = getS(S[i]);
        if (T[p].S[u] == 0) T[p].S[u] = ++idx;
        p = T[p].S[u];
    }
    T[p].end = true;
}

int Q[N], hh, tt;

void getFail()
{
    for (int u = 0; u < 4; u++)
        if (T[0].S[u])
            Q[tt++] = T[0].S[u];

    while (hh < tt)
    {
        int p = Q[hh++];
        T[p].end = T[p].end || T[T[p].fail].end;
        for (int u = 0; u < 4; u++)
        {
            int &q = T[p].S[u];
            if (q == 0) q = T[T[p].fail].S[u];
            else
            {
                T[q].fail = T[T[p].fail].S[u];
                Q[tt++] = q;
            }
        }
    }
}

int A[N][N];

void getMatrix()
{
    for (int p = 0; p <= idx; p++)
        for (int u = 0; u < 4; u++)
        {
            int q = T[p].S[u];
            if (!T[q].end) A[p][q]++;
        }
}

void mul(int C[N][N], int A[N][N], int B[N][N])
{
    static int tmp[N][N]; memset(tmp, 0, sizeof tmp);

    for (int i = 0; i <= idx; i++)
        for (int j = 0; j <= idx; j++)
            for (int k = 0; k <= idx; k++)
                tmp[i][j] = (tmp[i][j] + LL(A[i][k]) * B[k][j]) % MOD;

    memcpy(C, tmp, sizeof tmp);
}

int C[N][N];

void FP(int n)
{
    for (int i = 0; i <= idx; i++) C[i][i] = 1;
    while (n)
    {
        if (n & 1) mul(C, C, A);
        mul(A, A, A);
        n >>= 1;
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m; cin >> m >> n;
    for (int i = 0; i < m; i++)
    {
        cin >> S;
        ins();
    }
    getFail(); // 建立AC自动机

    getMatrix(); // 构建AC自动机的邻接矩阵

    FP(n); // 用矩阵快速幂递推状态

    int res = 0;
    for (int i = 0; i <= idx; i++) res = (res + C[0][i]) % MOD;
    cout << res << '\n';

    return 0;
}