AT_abc246_h [ABC246Ex] 01? Queries

题目描述

给定一个只包含 0、1、? 的长度为 $N$ 的字符串 $S$。

此外，给定 $Q$ 个查询 $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$。
其中，对于 $i = 1, 2, \ldots, Q$，$x_i$ 是满足 $1 \leq x_i \leq N$ 的整数，$c_i$ 是 0、1、? 中的任意一个字符。

请依次对每个查询 $(x_i, c_i)$ 执行以下操作：

1. 首先，将 $S$ 的第 $x_i$ 个字符（从前往后数）修改为 $c_i$。
2. 然后，输出将 $S$ 中所有的 ? 独立地替换为 0 或 1 后，所有可能得到的字符串的（不一定连续的）子序列中，所有可能出现的非空字符串的个数，结果对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出。

$N$ $Q$
$S$
$x_1$ $c_1$
$x_2$ $c_2$
$\vdots$
$x_Q$ $c_Q$

输出格式

输出 $Q$ 行。对于 $i = 1, 2, \ldots, Q$，第 $i$ 行输出第 $i$ 个查询 $(x_i, c_i)$ 的答案（即上述操作 2 中的字符串个数对 $998244353$ 取模的结果）。

输入输出样例 #1

输入 #1

3 3
100
2 1
2 ?
3 ?

输出 #1

5
7
10

输入输出样例 #2

输入 #2

40 10
011?0??001??10?0??0?0?1?11?1?00?11??0?01
5 0
2 ?
30 ?
7 1
11 1
3 1
25 1
40 0
12 1
18 1

输出 #2

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

说明/提示

限制条件

• $1 \leq N, Q \leq 10^5$
• $N, Q$ 为整数
• $S$ 是只包含 0、1、? 的长度为 $N$ 的字符串
• $1 \leq x_i \leq N$
• $c_i$ 是 0、1、? 中的任意一个字符

样例解释 1

• 第 1 个查询后，$S = 110$。作为 $S = 110$ 的子序列可能出现的字符串有：0、1、10、11、110，共 $5$ 个。因此，第 1 个查询的答案为 $5$。
• 第 2 个查询后，$S = 1?0$。将 ? 替换为 0 或 1 后得到的字符串为 100 和 110，它们的所有子序列可能出现的字符串有：0、1、00、10、11、100、110，共 $7$ 个。因此，第 2 个查询的答案为 $7$。
• 第 3 个查询后，$S = 1??$。将两个 ? 替换为 0 或 1 后得到的字符串为 100、101、110、111，它们的所有子序列可能出现的字符串有：0、1、00、01、10、11、100、101、110、111，共 $10$ 个。因此，第 3 个查询的答案为 $10$。

样例解释 2

请注意，答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译