logoChat01.ai

### Problem Statement You are given $N$ lowercase...

创建于：2025年8月16日

使用 GPT-5 Thinking 回答 Chat01

问题

Problem Statement

You are given NN lowercase English strings S1,S2,…,SNS_1,S_2,\ldots,S_N, and an integer LL.

Find the number, modulo 998244353998244353, of length-LL lowercase English strings that contain all of S1,S2,…,SNS_1,S_2,\ldots,S_N as substrings.

What is a substring? A substring of SS is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of SS.
For example, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

  • 1≤N≤81\leq N\leq 8
  • 1≤L≤1001\leq L\leq 100
  • NN and LL are integers.
  • Each SiS_i is a string of length 11 and 1010, inclusive, consisting of lowercase English letters.
  • Si≠Sj (i≠j)S_i\neq S_j\ (i\neq j)

Input

The input is given from Standard Input in the following format:

text
$N$ $L$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Output the answer.

Sample Input 1

text
2 4
ab
c

Sample Output 1

153

Some of the strings that satisfy the condition are abcz and cabc. acbd does not contain ab as a substring, so it does not satisfy the condition.

Sample Input 2

text
2 6
abc
cde

Sample Output 2

54

Sample Input 3

text
5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj

Sample Output 3

689020583

中文c++回答。

思考

Considering automata approach

I need to solve the problem in Chinese and implement it in C++. We’ll count strings of length L that contain all the given patterns as substrings. Aho-Corasick could be useful here. I'll use dynamic programming to track positions and matching patterns, considering complexities like redundant patterns and other edge cases.

Optimizing with Aho-Corasick

The problem requires us to count strings containing all given patterns as substrings. If one pattern is a substring of another, Aho-Corasick already handles it. We might consider pre-processing to remove dominated patterns, but it’s not strictly necessary. I'll focus on the typical Aho-Corasick setup with dynamic programming.

Optimizing memory usage and DP

I’m considering memory usage for the DP table since we’re dealing with around 2 million entries. To improve efficiency, I can compress the position dimension to reduce memory. The expected complexity seems manageable, around 53 million operations. I'll use long integers for modulo operations and optimize BFS during the Aho-Corasick construction.

Aho-Corasick construction

To build the Aho-Corasick automaton, we’ll compute the next (child) transitions, fail links, and 'go' edges. If a child doesn’t exist, we fall back on the fail link’s transition. Using BFS, I’ll initialize the queue and ensure we properly handle the next transitions and the fail link updates.

Thought for 47s

回答

下面给出一种标准做法：用 Aho–Corasick 自动机统计“匹配到哪些模式串”的状态，并在长度为 LL 的位置上做 DP。
设自动机有 K 个节点、模式数为 N(≤8)，用一个 mask（0…2N−12^N-1）表示已经出现过的模式集合。转移时对 26 个字母走自动机边，并把到达节点携带的输出位并入 mask。在长度 LL 处、mask == (1<<N)-1 的所有状态之和即为答案。取模 998244353998244353。

时间复杂度约为 O(L⋅K⋅26⋅2N)O(L \cdot K \cdot 26 \cdot 2^N)，这里 K≤∑∣Si∣≤80K \le \sum |S_i| \le 80，因此完全可行。
注意：若某个模式是另一个模式的子串，AC 自动机的失败链接与输出集合会自然处理，无需手动去重。

C++ 实现（中文注释）

cpp
#include <bits/stdc++.h>
using namespace std;

static const int MOD = 998244353;

struct AC {
    struct Node {
        int nxt[26];
        int fail;
        int outMask; // 该节点（及其通过fail传播后）代表出现了哪些模式
        Node() : fail(0), outMask(0) {
            fill(nxt, nxt + 26, -1);
        }
    };
    vector<Node> t;

    AC() { t.emplace_back(); } // root = 0

    void insert(const string &s, int id) {
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[u].nxt[c] == -1) {
                t[u].nxt[c] = (int)t.size();
                t.emplace_back();
            }
            u = t[u].nxt[c];
        }
        t[u].outMask |= (1 << id);
    }

    void build() {
        queue<int> q;
        // 初始化 root 的 26 条“自动转移”
        for (int c = 0; c < 26; ++c) {
            int v = t[0].nxt[c];
            if (v == -1) t[0].nxt[c] = 0;
            else {
                t[v].fail = 0;
                q.push(v);
            }
        }
        // BFS 构建 fail，并把输出集合沿 fail 传播
        while (!q.empty()) {
            int u = q.front(); q.pop();
            t[u].outMask |= t[t[u].fail].outMask;
            for (int c = 0; c < 26; ++c) {
                int v = t[u].nxt[c];
                if (v == -1) t[u].nxt[c] = t[t[u].fail].nxt[c];
                else {
                    t[v].fail = t[t[u].fail].nxt[c];
                    q.push(v);
                }
            }
        }
    }
};

int addmod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

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

    int N, L;
    if (!(cin >> N >> L)) return 0;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];

    AC ac;
    for (int i = 0; i < N; ++i) ac.insert(S[i], i);
    ac.build();

    int K = (int)ac.t.size();
    int M = 1 << N;
    int FULL = M - 1;

    // 滚动数组 dp[pos%2][state * M + mask]
    vector<int> dp0(K * M, 0), dp1(K * M, 0);
    dp0[0] = 1; // 长度0，处于root、mask=0

    for (int pos = 0; pos < L; ++pos) {
        fill(dp1.begin(), dp1.end(), 0);
        for (int st = 0; st < K; ++st) {
            int base = st * M;
            for (int mask = 0; mask < M; ++mask) {
                int cur = dp0[base + mask];
                if (!cur) continue;
                // 尝试 26 个字母
                for (int c = 0; c < 26; ++c) {
                    int ns = ac.t[st].nxt[c];
                    int nmask = mask | ac.t[ns].outMask;
                    int idx = ns * M + nmask;
                    dp1[idx] = addmod(dp1[idx], cur);
                }
            }
        }
        dp0.swap(dp1);
    }

    int ans = 0;
    for (int st = 0; st < K; ++st) {
        ans = addmod(ans, dp0[st * M + FULL]);
    }
    cout << ans << '\n';
    return 0;
}

说明要点

  • 利用 AC 自动机，把所有模式串同时“嵌入”到转移结构中；失败指针的输出集合 outMask 确保任意匹配均被记录。
  • dp[pos][state][mask] 只保留两层（滚动），节省内存。
  • 最终在长度 LL 统计 mask==FULL 的所有状态的计数和。

分享这个问答