[AdditionalFile4879.zip](file://AdditionalFile4879.zip?type=additional_file)

#4879. 「PA 2025」Podciągi

标签: 传统 | 时间限制: 15000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2025 Runda 5 Podciągi

你有一个长度为 $n$ 的字符串 $s$，由字母集 $\{\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}, \texttt{e}, \texttt{f}\}$ 组成。接下来会对它进行 $q$ 次操作，每次操作是替换字符串中的一个字母。

考虑字符串 $s$ 的所有子序列集合 $X_{s}$，也就是通过删除某些字母后得到的所有可能字符串（多重集）。

你的任务是跟踪一个信息：在 $X_{s}$ 中，有多少不同的非空字符串 $t$ 至少出现了两次。

比如，对于字符串 $\texttt{ababa}$，有 $6$ 个这样的字符串 $t$：

• 字符串 $\texttt{a}$ 在 $X_{s}$ 中出现 $3$ 次。
• 字符串 $\texttt{b}$ 在 $X_{s}$ 中出现 $2$ 次。
• 字符串 $\texttt{ab}$ 在 $X_{s}$ 中出现 $3$ 次（分别删去位置 $3,4,5$；$2,3,5$ 或 $1,2,5$ 的字母）。
• 字符串 $\texttt{ba}$ 在 $X_{s}$ 中出现 $3$ 次（分别删去位置 $1,4,5$；$1,3,4$ 或 $1,2,3$ 的字母）。
• 字符串 $\texttt{aa}$ 在 $X_{s}$ 中出现 $3$ 次（分别删去位置 $2,4,5$；$2,3,4$ 或 $1,2,4$ 的字母）。
• 字符串 $\texttt{aba}$ 在 $X_{s}$ 中出现 $4$ 次（分别删去位置 $4,5$；$3,4$；$2,3$ 或 $1,2$ 的字母）。

请你算出初始字符串 $s$ 以及每次操作后 $s$ 的 $X_{s}$ 中符合条件的字符串 $t$ 的数量。因为这些数字可能很大，输出它们对 $998244353$ 取模的结果。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ $(3 \leq n \leq 50000, 0 \leq q \leq 50000)$，分别表示字符串长度和操作次数。

第二行是一个长度为 $n$ 的字符串，仅由小写字母 $\texttt{a}$ 到 $\texttt{f}$ 组成。

接下来的 $q$ 行描述操作，每行包含一个整数 $p_{i}$ $(1 \leq p_{i} \leq n)$ 和一个字母 $z_{i}$ $(z_{i} \in \{\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}, \texttt{e}, \texttt{f}\})$，表示将 $s$ 中第 $p_{i}$ 位置的字母替换为 $z_{i}$。

输出格式

输出 $q+1$ 行，每行一个整数。第 $i$ 行表示初始状态或前 $i-1$ 次操作后的 $s$ 中，$X_{s}$ 内至少出现两次的不同字符串 $t$ 的数量，结果对 $998244353$ 取模。

样例

输入

4 3
abca
1 a
4 d
2 c

输出

1
1
0
4

以下是字符串 $s$ 在每次更新后的状态，以及作为 $s$ 子序列至少出现两次的字符串 $t$：

• 字符串：$\texttt{abca}$，子序列：$\{\texttt{a}\}$
• 字符串：$\texttt{abca}$，子序列：$\{\texttt{a}\}$
• 字符串：$\texttt{abcd}$，子序列：$\{\}$
• 字符串：$\texttt{accd}$，子序列：$\{\texttt{ac, acd, cd, c}\}$