← 返回题目列表

AtCoder · abc246_h

Ex. 01?查询

中文机器翻译题面 查看原题

分数: 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).

  1. 首先,更改 x_i- 从开头算起的第一个字符 S to c_i.
  2. 然后,打印非空字符串的数量,模 998244353,可以作为(不一定是连续的)子序列获得 S 替换每次出现的 ? in S 与 0 or 1 独立。

约束

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