提出 #75869291

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int ALPH = 26;
const int MAX_NODES = 101;
struct Matrix {
    int sz;
    vector<vector<int>> a;
    Matrix(int n) : sz(n), a(n, vector<int>(n, 0)) {}
    Matrix operator*(const Matrix& other) const {
        Matrix res(sz);
        for (int i = 0; i < sz; ++i)
            for (int k = 0; k < sz; ++k)
                if (a[i][k])
                    for (int j = 0; j < sz; ++j)
                        res.a[i][j] = (res.a[i][j] + (ll)a[i][k] * other.a[k][j]) % MOD;
        return res;
    }
};
Matrix mat_pow(Matrix base, ll exp) {
    int n = base.sz;
    Matrix res(n);
    for (int i = 0; i < n; ++i) res.a[i][i] = 1;
    while (exp) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}
struct AhoNode {
    int next[ALPH];
    int fail;
    bool danger;
};
vector<AhoNode> trie;
void insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!trie[u].next[c]) {
            trie[u].next[c] = trie.size();
            trie.emplace_back();
        }
        u = trie[u].next[c];
    }
    trie[u].danger = true;
}
void build_fail() {
    queue<int> q;
    for (int c = 0; c < ALPH; ++c) {
        int v = trie[0].next[c];
        if (v) {
            trie[v].fail = 0;
            q.push(v);
        } else {
            trie[0].next[c] = 0;
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        trie[u].danger |= trie[trie[u].fail].danger;
        for (int c = 0; c < ALPH; ++c) {
            int v = trie[u].next[c];
            if (v) {
                trie[v].fail = trie[trie[u].fail].next[c];
                q.push(v);
            } else {
                trie[u].next[c] = trie[trie[u].fail].next[c];
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    int K;
    cin >> N >> K;
    trie.clear();
    trie.emplace_back();
    for (int i = 0; i < K; ++i) {
        string s;
        cin >> s;
        insert(s);
    }
    build_fail();
    vector<int> good_nodes;
    for (int i = 0; i < (int)trie.size(); ++i) {
        if (!trie[i].danger) good_nodes.push_back(i);
    }
    int M = good_nodes.size();
    vector<int> id(trie.size(), -1);
    for (int i = 0; i < M; ++i) id[good_nodes[i]] = i;
    Matrix mat(M);
    for (int i = 0; i < M; ++i) {
        int u = good_nodes[i];
        for (int c = 0; c < ALPH; ++c) {
            int v = trie[u].next[c];
            if (!trie[v].danger) {
                int j = id[v];
                mat.a[i][j] = (mat.a[i][j] + 1) % MOD;
            }
        }
    }
    Matrix matN = mat_pow(mat, N);
    vector<int> init(M, 0);
    init[id[0]] = 1;
    ll ans = 0;
    for (int i = 0; i < M; ++i) {
        ll sum = 0;
        for (int k = 0; k < M; ++k) {
            sum = (sum + (ll)init[k] * matN.a[k][i]) % MOD;
        }
        ans = (ans + sum) % MOD;
    }
    cout << ans;
    return 0;
}

提出情報

ジャッジ結果