ACAC 题库 ac.isam.top
GitHub
SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）
F
致命误读
Critical Misread
AtCoder
⌀ 1744
原题
←G →

致命误读AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given $K$ strings $S_i$ consisting of lowercase English letters. Find the number, modulo $998244353$, of strings of length $N$ consisting of lowercase English letters that do not contain any of $S_1, S_2, \dots, S_K$ as a substring (contiguous subsequence).

给定 $K$ 个由小写英文字母组成的字符串 $S_i$。

请求出满足以下条件的、由小写英文字母组成的长度为 $N$ 的字符串数量，答案对 $998244353$ 取模：这些字符串中不包含 $S_1, S_2, \dots, S_K$ 中的任何一个作为子串（连续子序列）。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $N$ is an integer between $1$ and $10^9$, inclusive.
  • $K$ is an integer between $1$ and $10$, inclusive.
  • $S_i$ is a string consisting of lowercase English letters with length between $1$ and $10$, inclusive.
  • $N$ 是一个介于 $1$ 和 $10^9$ 之间（含端点）的整数。
  • $K$ 是一个介于 $1$ 和 $10$ 之间（含端点）的整数。
  • $S_i$ 是一个由小写英文字母组成的字符串，长度介于 $1$ 和 $10$ 之间（含端点）。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

输入从标准输入按以下格式给出：AI (CI翻译)

N K
S_1
S_2
\vdots
S_K

N K
S_1
S_2
\vdots
S_K
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer.

输出答案。AI (CI翻译)

样例

Input #1
3 2
aa
ab
Output #1
17474
- The number of strings of length $3$ consisting of lowercase English letters is $26^3=17576$. - The number of strings of length $3$ consisting of lowercase English letters whose first two characters are `aa` is $26$. - The number of strings of length $3$ consisting of lowercase English letters whose last two characters are `aa` is $26$. - The number of strings of length $3$ consisting of lowercase English letters whose first two characters are `ab` is $26$. - The number of strings of length $3$ consisting of lowercase English letters whose last two characters are `ab` is $26$. - The number of strings of length $3$ consisting of lowercase English letters whose entirety is `aaa` is $1$. - The number of strings of length $3$ consisting of lowercase English letters whose entirety is `aab` is $1$. - Combining the above facts, it can be confirmed that the answer for this test case is $17474$.
Input #2
1 1
ab
Output #2
26
Input #3
1000000000 10
contest
tester
error
orange
angel
elegant
antitese
sextuple
pleasure
surely
Output #3
698570468
Find the count modulo $998244353$.
题目信息
题号
abc458_f
所属比赛
SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。