POJ 2778

众所周知，DNA序列是仅包含A、C、T和G的序列，对于分析DNA序列的一个片段非常有用。例如，如果一个动物的DNA序列包含片段ATC，那么这可能意味着这个动物可能患有遗传疾病。到目前为止，科学家已经发现了几个这样的片段，问题是一个物种的DNA序列中有多少种不包含这些片段的序列。

假设一个物种的DNA序列是由A、C、T和G组成的序列，序列的长度是给定的整数n。

输入

第一行包含两个整数m（0 <= m <= 10）、n（1 <= n <= 2000000000）。这里，m是遗传疾病片段的数量，n是序列的长度。

接下来的m行，每行包含一个DNA遗传疾病片段，这些片段的长度不超过10。

输出

一个整数，表示DNA序列的数量，取模100000后的结果。

#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using namespace std;

const int MAXN = 105;
const int MOD = 100000;

struct Matrix { // 矩阵
    int n;
    long long a[MAXN][MAXN];

    Matrix() {
        memset(a, 0, sizeof a);
    }

    Matrix(int _n) {
        n = _n;
        memset(a, 0, sizeof a);
    }

    long long* operator[](int x) {
        return a[x];
    }

    friend Matrix operator*(Matrix a, Matrix b) {
        int n = a.n;
        Matrix ans(n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    ans[i][j] = (ans[i][j] + 1ll * a[i][k] * b[k][j]) % MOD;
        return ans;
    }

    friend Matrix operator^(Matrix a, long long x) {
        int n = a.n;
        Matrix ans(n);
        for (int i = 0; i < n; i++)
            ans[i][i] = 1;
        while (x) {
            if (x & 1)
                ans = ans * a;
            a = a * a;
            x >>= 1;
        }
        return ans;
    }
};
const int C = 4;

int cnt = 1;
int t[MAXN][C];
bool flag[MAXN];
int fail[MAXN];
int id[MAXN];

int hsh(char c) { // 将字符转化为数字
    if (c == 'A')
        return 0;
    if (c == 'C')
        return 1;
    if (c == 'T')
        return 2;
    if (c == 'G')
        return 3;
}

void insert(string s) { // 插入字典树
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        int v = hsh(c);
        // cerr << p << " " << cnt << " " << t[p][v] << endl;
        if (!t[p][v])
            t[p][v] = cnt++;
        p = t[p][v];
    }
    flag[p] = true;
}

void getfail() { // 构建字典图
    queue<int> q;
    for (int i = 0; i < C; i++)
        if (t[0][i])
            q.push(t[0][i]);
    while (q.size()) {
        int u = q.front();
        // cerr << u << endl;
        q.pop();
        for (int i = 0; i < C; i++) {
            if (t[u][i])
                fail[t[u][i]] = t[fail[u]][i], q.push(t[u][i]);
            else
                t[u][i] = t[fail[u]][i];
        }
    }
}

int query(long long n) { // 统计邻接矩阵并统计答案
    int ids = 0;
    memset(id, 0xff, sizeof id);
    for (int i = 0; i < cnt; i++)
        if (!flag[i])
            id[i] = ids++;
    Matrix F(ids);
    for (int u = 0; u < cnt; u++) {
        if (flag[u])
            continue;
        for (int i = 0; i < C; i++) {
            int v = t[u][i];
            if (flag[v])
                continue;
            F[id[u]][id[v]]++;
            // cerr << id[u] << " " << id[v] << " " << u << " " << v << endl;
        }
    }
    cnt = ids;
    F = F ^ n;
    int res = 0;
    for (int i = 0; i < cnt; i++)
        res = (res + F[0][i]) % MOD;
    return res;
}

long long m, n;

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

    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        string tmp;
        cin >> tmp;
        insert(tmp);
    }

    getfail();
    cout << query(n) << endl;

    return 0;
}