P11928 [PA 2025] 子序列 / Podciągi

PA 2025 R5B. **警告：滥用本题评测一次即可封号。**

本题中下标均为 $\text{1-indexed}$。 给定长度为 $n$ 的字符串 $s$，字符集 $\Sigma=\{\texttt{a},\texttt{b},\ldots,\texttt{f}\}$。 有 $q$ 次操作，每次操作对 $s$ 进行单点修改。 对于 $i=1,2,\ldots,q+1$，求出：进行前 $(i-1)$ 次操作后，$s$ 中满足以下条件的**非空**子序列 $t$ 的数量： - $t$ 在 $s$ 中出现至少两次。 由于答案可能很大，只需要求出答案对 $998\, 244\, 353$ 取模后的结果。

第一行，两个非负整数 $n,q$。 第二行，字符串 $s$。 接下来 $q$ 行，第 $i$ 行正整数 $p_i$ 和字符 $c_i$，表示一次操作 $s_{p_i}\gets c_i$。

输出 $(q+1)$ 行，第 $i$ 行一个非负整数，表示进行前 $(i-1)$ 次操作后的答案对 $998\, 244\, 353$ 取模后的结果。

### 样例解释 - 初始字符串为 $s=\texttt{abca}$，唯一符合条件的子序列为 $\texttt{a}$。 - 进行 $1$ 次操作后，字符串为 $s=\texttt{abca}$，唯一符合条件的子序列为 $\texttt{a}$。 - 进行前 $2$ 次操作后，字符串为 $s=\texttt{abcd}$，无符合条件的子序列。 - 进行前 $3$ 次操作后，$s=\texttt{accd}$，符合条件的子序列有 $\texttt{ac},\texttt{cd},\texttt{acd},\texttt{c}$。 ### 子任务 存在大于 $0$ 分的子任务满足 $\Sigma=\{\texttt{a},\texttt{b}\}$。 ### 数据范围 - $3 \le n \le 5\times 10^4$； - $0 \le q \le 5\times 10^4$； - $s_i,c_i\in \Sigma=\{\texttt{a},\texttt{b},\ldots,\texttt{f}\}$； - $1\le p_i\le n$。