Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 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) に関して以下の処理を行ってください。
- まず、S の先頭から x_i 文字目を c_i に変更する。
- その後、「 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).
- 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.