Score : $600$ points

问题描述

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

同时，你也将获得 $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 或 ? 中的一个。

按照 $i = 1, 2, \ldots, Q$ 的顺序，对查询 $(x_i, c_i)$ 执行以下过程：

1. 首先，将字符串 $S$ 开头的第 $x_i$ 个字符更改为 $c_i$。
2. 然后，计算在将 $S$ 中出现的所有 ? 独立替换为 0 或 1 后，可以获得的非空子序列（不一定是连续子串）的数量，并对 $998244353$ 取模后输出这个数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a string $S$ of length $N$ consisting of 0, 1, and ?.

You are also given $Q$ queries $(x_1, c_1), (x_2, c_2), \ldots, (x_Q, c_Q)$.
For each $i = 1, 2, \ldots, Q$, $x_i$ is an integer satisfying $1 \leq x_i \leq N$ and $c_i$ is one of the characters 0 , 1, and ?.

For $i = 1, 2, \ldots, Q$ in this order, do the following process for the query $(x_i, c_i)$.

1. First, change the $x_i$-th character from the beginning of $S$ to $c_i$.
2. Then, print the number of non-empty strings, modulo $998244353$, that can be obtained as a (not necessarily contiguous) subsequence of $S$ after replacing each occurrence of ? in $S$ with 0 or 1 independently.

Constraints

• $1 \leq N, Q \leq 10^5$
• $N$ and $Q$ are integers.
• $S$ is a string of length $N$ consisting of 0, 1, and ?.
• $1 \leq x_i \leq N$
• $c_i$ is one of the characters 0 , 1, and ?.

Input

Input is given from Standard Input in the following format:

$N$ $Q$

$S$

$x_1$ $c_1$

$x_2$ $c_2$

$\vdots$

$x_Q$ $c_Q$

Output

Print $Q$ lines. For each $i = 1, 2, \ldots, Q$, the $i$-th line should contain the answer to the $i$-th query $(x_i, c_i)$ (that is, the number of strings modulo $998244353$ at the step 2. in the statement).

Sample Input 1

3 3
100
2 1
2 ?
3 ?

Sample Output 1

5
7
10

• The $1$-st query starts by changing $S$ to 110. Five strings can be obtained as a subsequence of $S =$ 110: 0, 1, 10, 11, 110. Thus, the $1$-st query should be answered by $5$.

• The $2$-nd query starts by changing $S$ to 1?0. Two strings can be obtained by the ? in $S =$ 1?0: 100 and 110. Seven strings can be obtained as a subsequence of one of these strings: 0, 1, 00, 10, 11, 100, 110. Thus, the $2$-nd query should be answered by $7$.

• The $3$-rd query starts by changing $S$ to 1??. Four strings can be obtained by the ?'s in $S =$ 1??: 100, 101, 110, 111. Ten strings can be obtained as a subsequence of one of these strings: 0, 1, 00, 01, 10, 11, 100, 101, 110, 111. Thus, the $3$-rd query should be answered by $10$.

Sample Input 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

Sample Output 2

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

Be sure to print the count modulo $998244353$.

update @ 2024/3/10 10:34:46