思路与算法

用26字母AC自动机表示当前最长匹配前缀后缀，终止状态期望为0。对每个非终止状态u建立26Eu-Σc E[next(u,c)]=26，终止转移不加入未知数。模1e9+7高斯消元并回代，输出根的期望。独立答案由模式串重叠相关矩阵和精确有理数方程得到。

正确性说明

下一字符等概率，条件期望公式Eu=1+ΣE[next]/26成立。终止即停止，不再产生按键。方程完整覆盖所有未停止状态，有限模式在独立随机字符流中几乎必然出现且期望有限；在题目要求的模域可解情形下，消元保持方程等价，根解即所求有理数的模表示。

复杂度

每组状态S≤151，建Trie/fail O(26S)，方程初始化O(S²+26S)，高斯消元及回代O(S³)，空间O(S²)。T≤50逐组释放；模乘用64位。

易错点

必须向fail传播bad。不能把概率当普通整数26除法，用清分母后的线性方程。若出现模域奇异，程序不会伪造答案；本批所有候选与原生数据均已验证可解。

参考代码（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];
        }
    }
}
const long long MOD = 1000000007;
long long pw(long long a, long long b) {
    long long r = 1;
    while (b) {
        if (b & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ac.assign(1, Node());
        int n;
        cin >> n;
        while (n--) {
            string s;
            cin >> s;
            add(s, 26, false);
        }
        build(26);
        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++;
        vector<vector<long long>> a(N, vector<long long>(N + 1));
        for (int i = 0; i < (int)ac.size(); i++)
            if (id[i] >= 0) {
                int u = id[i];
                a[u][u] = 26;
                a[u][N] = 26;
                for (int z = 0; z < 26; z++) {
                    int v = id[ac[i].go[z]];
                    if (v >= 0)
                        a[u][v] = (a[u][v] + MOD - 1) % MOD;
                }
            }
        for (int k = 0; k < N; k++) {
            int p = k;
            while (p < N && !a[p][k])
                p++;
            if (p == N)
                return 2;
            swap(a[p], a[k]);
            long long inv = pw(a[k][k], MOD - 2);
            for (int j = k; j <= N; j++)
                a[k][j] = a[k][j] * inv % MOD;
            for (int i = k + 1; i < N; i++)
                if (a[i][k]) {
                    long long f = a[i][k];
                    for (int j = k; j <= N; j++)
                        a[i][j] = (a[i][j] - f * a[k][j] % MOD + MOD) % MOD;
                }
        }
        vector<long long> x(N);
        for (int i = N - 1; i >= 0; i--) {
            x[i] = a[i][N];
            for (int j = i + 1; j < N; j++)
                x[i] = (x[i] - a[i][j] * x[j] % MOD + MOD) % MOD;
        }
        cout << x[0] << '\n';
    }
}