102467: [AtCoder]ABC246 Ex - 01? Queries
Description
Score : $600$ points
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)$.
- First, change the $x_i$-th character from the beginning of $S$ to $c_i$.
- 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$ with0
or1
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
and110
. 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$.
Input
题意翻译
给定长度为 $N$ 的仅包含 `0`,`1`,`?` 的字符串 $S$,给定 $Q$ 组询问 $(x_1, c_1), (x_2, c_2), \cdots, (x_q, c_q)$,每次将原字符串中 $x_i$ 位置的字符改为 $c_i$,然后输出 $S$ 有多少种非空子序列,`?` 需任意替换为 `0` 或 `1`。 $1 \le N, Q \le 10^5, 1 \le x_i \le N$。Output
110
。可以作为S的子序列得到的S字符串有5个:0
,1
,10
,11
,110
。因此,第1个查询的答案应为5。
- 第2个查询开始时将S改为1?0
。可以通过S中的?
得到的字符串有2个:100
和110
。可以作为其中一个字符串的子序列得到的字符串有7个:0
,1
,00
,10
,11
,100
,110
。因此,第2个查询的答案应为7。
- 第3个查询开始时将S改为1??
。可以通过S中的?
's得到的字符串有4个:100
,101
,110
,111
。可以作为其中一个字符串的子序列得到的字符串有10个:0
,1
,00
,01
,10
,11
,100
,101
,110
,111
。因此,第3个查询的答案应为10。
部分
样例输入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