Ex - 01? Queries Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

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 、? のうちのいずれかの文字です。

i = 1, 2, \ldots, Q の順に、クエリ (x_i, c_i) に関して以下の処理を行ってください。

  1. まず、S の先頭から x_i 文字目を c_i に変更する。
  2. その後、「 S に含まれるすべての ? をそれぞれ独立に 0 または 1 に置き換えて得られる文字列の（連続とは限らない）部分列」としてあり得る空でない文字列の個数を、998244353 で割ったあまりを出力する。

制約

  • 1 \leq N, Q \leq 10^5
  • N, Q は整数
  • S は 0 、1 、? のみからなる長さ N の文字列
  • 1 \leq x_i \leq N
  • c_i は 0 、1 、? のうちいずれかの文字

入力

入力は以下の形式で標準入力から与えられる。

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

3 3
100
2 1
2 ?
3 ?

出力例 1

5
7
10

  • 1 個目のクエリで、まず S = 110 に変更されます。S = 110 の部分列としてあり得る文字列は、0 、1 、10 、11 、110 の 5 個です。よって、1 個目のクエリに対する答えとして 5 を出力します。

  • 2 個目のクエリで、まず S = 1?0 に変更されます。S = 1?0 の ? を 0 または 1 に置き換えて得られる文字列は、100 と 110 の 2 つです。 これらのどちらかの部分列としてあり得る文字列は、0 、1 、00 、10 、11 、100 、110 の 7 個です。よって、2 個目のクエリに対する答えとして 7 を出力します。

  • 3 個目のクエリで、まず S = 1?? に変更されます。S = 1?? の ? を 0 または 1 に置き換えて得られる文字列は、100、 101、 110、 111 の 4 つです。 これらのいずれかの部分列としてあり得る文字列は、0 、1 、00 、01 、10 、11 、100 、101 、110 、111 の 10 個です。よって、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

出力例 2

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

998244353 で割ったあまりを出力することに注意してください。

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).

  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.