← 返回题目列表

Codeforces · 1488/H

H. 从后缀构建

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

给定一个整数 $$$n$$$ 和一个 $$$n-1$$$ 整数的序列 $$$a$$$,每个元素要么是 $$$0$$$ 要么是 $$$1$$$。

您需要构建一个长度为 $$$n$$$ 的字符串,使得:

- 每个字母都是“abcd”之一;
- 如果 $$$a_i=1$$$,则字符串的第 $$$i$$$ 个后缀按字典顺序小于第 $$$(i+1)$$$ 个后缀;
- 如果 $$$a_i=0$$$,则字符串的第 $$$i$$$ 个后缀按字典顺序大于第 $$$(i+1)$$$ 个后缀。

您将被询问 $$$q$$$ 形式的查询:

- $$$i$$$ ($$$1 \le i \le n - 1$$$) — 翻转 $$$a_i$$$ 的值(如果 $$$a_i=0$$$,则将 $$$a_i$$$ 设置为 $$$1$$$,反之亦然)。

在每个查询后打印满足给定约束模 $$$998\,244\,353$$$ 的不同字符串的数量。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) - 字符串的长度和查询的数量。

第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$a_i \in \{0, 1\}$$$) - 对字符串后缀的约束。

接下来的 $$$q$$$ 行都包含一个查询:一个整数 $$$i$$$ ($$$1 \le i \le n - 1$$$) — 翻转 $$$a_i$$$ 的值(如果 $$$a_i=0$$$,则将 $$$a_i$$$ 设置为 $$$1$$$,反之亦然)。

输出

在每个查询后打印满足给定约束模 $$$998\,244\,353$$$ 的不同字符串的数量。

示例

输入 #1

2 2
0
1
1

输出 #1

6
10

输入 #2

3 4
0 0
1
2
1
2

输出 #2

20
10
14
20

输入 #3

10 10
0 0 0 1 1 1 0 1 0
4
1
8
4
2
9
5
6
6
8

输出 #3

1815
3201
2710
2776
2290
1644
2668
1271
2668
2436

注意

字符串的第 $$$i$$$ 后缀是从第 $$$i$$$ 个位置开始到最后一个位置结束的连续子字符串。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

如果存在 $$$i$$$ 位置使得 $$$a_i \neq b_i$$$,则长度为 $$$n$$$ 的两个字符串 $$$a$$$ 和 $$$b$$$ 会有所不同。