AT_1_ttpc2024_1_b.Self Checkout

给你一个由数字 1, 2, 3 组成且长度为 $N$ 的数列 $S$。请找出所有由数字 1 和 2 组成的数列 $A$，使通过一定的操作后，生成的数列 $T$ 等于 $S$。我们要计算这样的数列 $A$ 的个数，并对结果取 $998244353$ 的余数。可以证明，符合要求的数列 $A$ 的个数是有限的。

操作描述如下：

1. 初始化变量 $C = 0$。
2. 如果数列 $A$ 中存在数字 1，将最前面的一个 1 移除，并将 $C$ 加 1。
3. 如果此时 $A$ 仍然不为空，移除 $A$ 的第一个元素 $x$，并将 $C$ 加上 $x$ 的值。
4. 将 $C$ 添加到数列 $T$ 的末尾。
5. 如果此时 $A$ 为空，操作结束；否则，返回步骤 1。

输入包含两个部分：

• 一个整数 $N$，代表数列 $S$ 的长度。
• 接下来是 $N$ 个整数，分别是 $S_1, S_2, \dots, S_N$。

输出满足条件的数列 $A$ 的个数，对 $998244353$ 取余的结果。

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

样例解释 1

如果 $S = (3, 2)$，则满足条件的数列 $A$ 有 $(1, 2, 2)$, $(2, 1, 2)$, $(2, 2, 1)$, $(2, 1, 1, 1)$ 和 $(1, 2, 1, 1)$，共 5 种。例如，对于 $A = (2, 1, 1, 1)$：

• 移除 $A$ 中首个 $1$，此时 $A = (2, 1, 1)$，$C = 1$。
• 移除 $A$ 的第一个元素 2，此时 $A = (1, 1)$，$C = 3$。
• 把 $C$ 加入 $T$，得到 $T = (3)$。
• 再移除 $A$ 中首个 $1$，此时 $A = (1)$，$C = 1$。
• 移除 $A$ 的第一个元素 1，$A$ 变为空，$C = 2$。
• 将 $C$ 加入 $T$，得到 $T = (3, 2)$。

样例解释 3

也有可能没有符合条件的数列 $A$，这种情况结果为 0。

本翻译由 AI 自动生成