← 返回题目列表

Codeforces · 1380/F

F. 奇怪的添加

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

设 $$$a$$$ 和 $$$b$$$ 为一些非负整数。让我们定义 $$$a$$$ 和 $$$b$$$ 的奇怪加法如下:

1. 逐个写下数字,并按最低有效数字对齐;
2. 将它们逐位相加,并将各自的和连接在一起。

假设两个数字都有无数个前导零。

例如,让我们看一下数字 $$$3248$$$ 和 $$$908$$$ 的奇怪加法:

给定一个字符串 $$$c$$$,由从 $$$0$$$ 到 $$$9$$$ 的 $$$n$$$ 数字组成。您还会收到以下形式的 $$$m$$$ 更新:

- $$$x~d$$$ — 将 $$$c$$$ 的第 $$$x$$$ 位置的数字替换为数字 $$$d$$$。

请注意,字符串 $$$c$$$ 在任何时间点都可能有前导零。

每次更新后,打印 $$$(a, b)$$$ 对的数量,使得 $$$a$$$ 和 $$$b$$$ 都是非负整数,并且 $$$a$$$ 和 $$$b$$$ 的奇怪加法结果等于 $$$c$$$。

请注意,对的数量可能非常大,因此请以 $$$998244353$$$ 为模打印它们。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$) — 数字 $$$c$$$ 的长度和更新次数。

第二行包含一个字符串 $$$c$$$,由从 $$$0$$$ 到 $$$9$$$ 的 $$$n$$$ 个数字组成。

接下来的 $$$m$$$ 行包含两个整数 $$$x$$$ 和 $$$d$$$ ($$$1 \le x \le n$$$, $$$0 \le d \le 9$$$) - 更新的描述。

输出

打印 $$$m$$$ 整数 - 第 $$$i$$$ 值应等于 $$$(a, b)$$$ 对的数量,这样 $$$a$$$ 和 $$$b$$$ 都是非负整数,并且 $$$a$$$ 和 $$$b$$$ 奇怪相加的结果等于 $$$c$$$ 之后应用 $$$i$$$ 更新。

请注意,对的数量可能非常大,因此请以 $$$998244353$$$ 为模打印它们。

示例

输入 #1

2 3
14
2 4
2 1
1 0

输出 #1

15
12
2

注意

第一次更新后 $$$c$$$ 等于 $$$14$$$。总和为 $$$14$$$ 的对是:$$$(0, 14)$$$、$$$(1, 13)$$$、$$$(2, 12)$$$、$$$(3, 11)$$$、$$$(4, 10)$$$、$$$(5, 9)$$$、$$$(6, 8)$$$、 $$$(7, 7)$$$, $$$(8, 6)$$$, $$$(9, 5)$$$, $$$(10, 4)$$$, $$$(11, 3)$$$, $$$(12, 2)$$$, $$$(13, 1)$$$, $$$(14, 0)$$$。

第二次更新后 $$$c$$$ 等于 $$$11$$$。

第三次更新后$$$c$$$ 等于$$$01$$$。