103056: [Atcoder]ABC305 G - Banned Substrings
Description
Score : $550$ points
Problem Statement
You are given a set $S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace$ of non-empty strings of length at most $6$ consisting of a and b.
Find the number of strings $T$ of length $N$ consisting of a and b that satisfy the following condition:
- $T$ does not contain $s _ i$ as a consecutive substring for any $s _ i\in S$.
Since the answer can be enormous, find it modulo $998244353$.
Constraints
- $1\leq N\leq10^{18}$
- $1\leq M\leq126$
- $N$ and $M$ are integers.
- $s _ i$ is a non-empty string of length at most $6$ consisting of
aandb. - $s _ i\neq s _ j\ (1\leq i\lt j\leq M)$
Input
The input is given from Standard Input in the following format:
$N$ $M$ $s _ 1$ $s _ 2$ $\vdots$ $s _ M$
Output
Print the answer modulo $998244353$ in a single line.
Sample Input 1
4 3 aab bbab abab
Sample Output 1
10
There are $10$ strings of length $4$ consisting of a and b that do not contain aab, bbab, or abab as consecutive substrings: aaaa, abaa, abba, abbb, baaa, baba, babb, bbaa, bbba, and bbbb. Thus, you should print $10$.
Sample Input 2
20 1 aa
Sample Output 2
17711
Sample Input 3
1000000007 28 bbabba bbbbaa aabbab bbbaba baaabb babaab bbaaba aabaaa aaaaaa aabbaa bbaaaa bbaabb bbabab aababa baaaba ababab abbaba aabaab ababaa abbbba baabaa aabbbb abbbab baaaab baabbb ababbb baabba abaaaa
Sample Output 3
566756841
Print the answer modulo $998244353$.
Input
题意翻译
## 题目描述： 给定一个由 $M$ 个长度不超过 6 的仅由字母 $a$ 和 $b$ 组成的非空字符串集合 $S=\{s_1, s_2, ..., s_M\}$ 和一个长度为 $N$ 的仅由字母 $a$ 和 $b$ 组成的字符串 $T$，求有多少个字符串 $T$ 满足以下条件： 对于任意 $s_i\in S$，$T$ 中不包含 $s_i$ 作为连续的子串。 由于答案可能很大，所以对 998244353 取模。 ## 数据范围: $1\leq N\leq 10^{18}$ $1\leq M\leq 126$ $N$ 和 $M$ 是整数。 $s_i$ 是由字母 $a$ 和 $b$ 组成的长度不超过 $6$ 的非空字符串。 $s_i \neq s_j$（$1\leq i<j\leq M$）。 ## 输入格式: 输入共 $M+1$ 行，第一行包括两个整数 $N$ 和 $M$，表示字符串长度和非空字符串集合大小。接下来 $M$ 行，每行一个字符串 $s_i$。 ## 输出格式: 输出仅包含一个整数，表示满足条件的字符串 $T$ 的个数对 998244353 取模后的结果。Output
问题描述
给你一个由非空字符串组成的集合$S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace$，其中字符串的长度最多为$6$，由字符a和b组成。
- 找出长度为$N$的由字符
a和b组成的字符串$T$，满足以下条件：$T$中不存在连续子串$s _ i$，其中$s _ i\in S$。
由于答案可能非常大，要求你输出答案模$998244353$的结果。
限制条件
- $1\leq N\leq10^{18}$
- $1\leq M\leq126$
- $N$和$M$为整数。
- $s _ i$是一个长度最多为$6$的非空字符串，由字符
a和b组成。 - $s _ i\neq s _ j\ (1\leq i\lt j\leq M)$
输入
输入从标准输入按以下格式给出：
$N$ $M$ $s _ 1$ $s _ 2$ $\vdots$ $s _ M$
输出
在一行中输出答案模$998244353$的结果。
样例输入1
4 3 aab bbab abab
样例输出1
10
长度为$4$的由字符a和b组成的字符串，不包含aab、bbab或abab作为连续子串的字符串有$10$个：aaaa、abaa、abba、abbb、baaa、baba、babb、bbaa、bbba和bbbb。因此，你应该输出$10$。
样例输入2
20 1 aa
样例输出2
17711
样例输入3
1000000007 28 bbabba bbbbaa aabbab bbbaba baaabb babaab bbaaba aabaaa aaaaaa aabbaa bbaaaa bbaabb bbabab aababa baaaba ababab abbaba aabaab ababaa abbbba baabaa aabbbb abbbab baaaab baabbb ababbb baabba abaaaa
样例输出3
566756841
输出答案模$998244353$的结果。