思路与算法

把禁止DNA串插入AC自动机，沿fail传播终止标记。只有未匹配任何禁止串的状态合法；四个字母给出合法状态之间的转移次数矩阵。矩阵n次幂从根出发的行和就是答案，模100000。

正确性说明

AC状态记录已读串的最长前缀后缀，bad包含当前或fail链上已出现的禁止串。保留非bad转移恰好逐字生成所有合法DNA串一遍。矩阵乘法按中间状态分类，幂次对应长度，因此行和准确。

复杂度

设总Trie状态S≤101，读入、建fail与清空O(4S)，矩阵初始化O(S²)，快速幂O(S³logn)时间，O(S²+S)空间。

易错点

禁止串之间可包含，不能只标记自身终止节点。一个字母可使多个转移落到同一状态，矩阵应累加而非置1；使用合数模100000，不需要求逆。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    array<int, 26> go;
    int fail;
    bool bad;
    Node() : fail(0), bad(false) {
        go.fill(0);
    }
};
vector<Node> ac(1);
void add(string s, int sigma, bool dna) {
    int u = 0;
    for (char c : s) {
        int z = dna ? string("ACTG").find(c) : c - 'a';
        if (!ac[u].go[z]) {
            ac[u].go[z] = ac.size();
            ac.emplace_back();
        }
        u = ac[u].go[z];
    }
    ac[u].bad = true;
}
void build(int sigma) {
    queue<int> q;
    for (int z = 0; z < sigma; z++)
        if (ac[0].go[z])
            q.push(ac[0].go[z]);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ac[u].bad |= ac[ac[u].fail].bad;
        for (int z = 0; z < sigma; z++) {
            int v = ac[u].go[z];
            if (v) {
                ac[v].fail = ac[ac[u].fail].go[z];
                q.push(v);
            } else
                ac[u].go[z] = ac[ac[u].fail].go[z];
        }
    }
}
using Mat = vector<vector<long long>>;
Mat mul(const Mat &a, const Mat &b) {
    int n = a.size();
    Mat c(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (a[i][k])
                for (int j = 0; j < n; j++)
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % 100000;
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    long long n;
    cin >> m >> n;
    while (m--) {
        string s;
        cin >> s;
        add(s, 4, true);
    }
    build(4);
    vector<int> id(ac.size(), -1);
    int N = 0;
    for (int i = 0; i < (int)ac.size(); i++)
        if (!ac[i].bad)
            id[i] = N++;
    Mat a(N, vector<long long>(N)), p = a;
    for (int i = 0; i < N; i++)
        p[i][i] = 1;
    for (int i = 0; i < (int)ac.size(); i++)
        if (id[i] >= 0)
            for (int z = 0; z < 4; z++)
                if (id[ac[i].go[z]] >= 0)
                    a[id[i]][id[ac[i].go[z]]]++;
    while (n) {
        if (n & 1)
            p = mul(p, a);
        a = mul(a, a);
        n >>= 1;
    }
    long long ans = 0;
    for (int j = 0; j < N; j++)
        ans = (ans + p[0][j]) % 100000;
    cout << ans << '\n';
}