← 返回题目列表

AtCoder · ttpc2024_1_b

B. 自助结账

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

分数: 100 点

问题陈述

给你一个序列 S 长度 N,由整数组成 1, 2,和 3。确定序列数 A 由整数组成 1 和 2 这样的序列 执行以下过程后获得的 T 匹配 S。输出答案取模 998244353。可以证明这样的序列的个数 A 是有限的。

从一个空序列开始 T。给定一个序列 A 由整数组成 1 和 2,执行以下过程以获得序列 T:

  1. 设置变量 C = 0.
  2. If A 包含至少一个 1,移除首次出现的 1 来自 A 并添加 1 to C.
  3. If A 不为空,移除第一个元素 x of A 并添加 x to C.
  4. 追加 C 到年底 T.
  5. If A 为空,终止该过程。否则,返回步骤1。

约束

  • 所有输入值均为整数。
  • 1 \le N \le 10^6
  • 1 \le S_i \le 3

输入

输入由标准输入按以下格式给出:

N
S_1 S_2 \dots S_N

输出

输出序列的数量 A 满足条件,取模 998244353.


示例输入 1

2
3 2

示例输出 1

5

有 5 可能的序列 A 产生的 T = (3, 2): A = (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 1, 1), (1, 2, 1, 1).

例如,对于 A = (2, 1, 1, 1),过程如下:

  • 删除第一次出现的 1 in A,即 A_2 = 1。现在 A = (2, 1, 1) 和 C = 1.
  • 删除第一个元素 A,即 A_1 = 2。现在 A = (1, 1) 和 C = 3.
  • 追加 C 到年底 T。现在 T = (3).
  • 删除第一次出现的 1 in A,即 A_1 = 1。现在 A = (1) 和 C = 1.
  • 删除第一个元素 A,即 A_1 = 1。现在 A = () 和 C = 2.
  • 追加 C 到年底 T。现在 T = (3, 2).

示例输入 2

6
3 2 2 3 2 1

示例输出 2

4

示例输入 3

5
3 2 1 3 2

示例输出 3

0

注意可能存在没有序列的情况 A 产生 S,在这种情况下答案是 0.