分数: 600 点
问题陈述
给你一个字符串 S 长度 N 组成 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).
- 首先,更改 x_i- 从开头算起的第一个字符 S to c_i.
- 然后,打印非空字符串的数量,模 998244353,可以作为(不一定是连续的)子序列获得 S 替换每次出现的
?in S 与0or1独立。
约束
- 1 \leq N, Q \leq 10^5
- N 和 Q 是整数。
- S 是一个长度为的字符串 N 组成
0,1,和?. - 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) (即字符串的数量模 998244353 在语句的步骤 2. 中)。
示例输入 1
3 3 100 2 1 2 ? 3 ?
示例输出 1
5 7 10
-
的 树的 1-st 查询通过更改开始 S to
110。可以得到五个字符串作为子序列 S =110:0,1,10,11,110。因此, 1-st 查询应由 5. -
的 树的 2-nd 查询通过更改开始 S to
1?0。可以得到两个字符串?in S =1?0:100和110。可以获得七个字符串作为这些字符串之一的子序列:0,1,00,10,11,100,110。因此, 2-nd 查询应由以下人员回答 7. -
的 树的 3-rd 查询通过更改开始 S to
1??。可以得到四个字符串?位于 S =1??:100,101,110,111。可以获得十个字符串作为这些字符串之一的子序列:0,1,00,01,10,11,100,101,110,111。因此, 3-rd 查询应由 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.