分数: 400 点
问题陈述
有一个网格,包括 N 单元格编号 1 to N.
最初,细胞 i (1 \le i \le N) 有一个整数 i \bmod 2 。您可以执行以下操作任意次数,可能为零:
- 选择单元格 l 和 r (l+1 < r)满足以下条件,并替换单元格中写入的每个整数 l+1, l+2, \dots, r-1 将整数写入单元格 l.
- 单元格中写入的整数 l 等于单元格中写入的整数 r.
- 单元格中写入的整数 i (l < i < r) 与单元格中写入的整数不同 l.
求模数 998244353,导致整数写入单元格的操作序列 i (1 \leq i \leq N) 是 A_i.
两个操作序列被认为是不同的当且仅当它们的长度不同或者存在正整数 t 不超过序列的长度,使得 (l, r) 选择于 t-th 操作不同。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 1
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
6 1 1 1 1 1 0
示例输出 1
3
使每个单元格中写入整数 以 i 等于 A_i为例,您可以执行以下操作。 (在这里,我们将网格的状态表示为一个序列 X = (X_1, X_2, \dots, X_N).)
- 最初, X = (1, 0, 1, 0, 1, 0).
- 选择单元格 2 和 4. X 变为 (1, 0, 0, 0, 1, 0).
- 选择单元格 1 和 5. X 变为 (1, 1, 1, 1, 1, 0).
除了上述之外,还有另外两个操作序列会导致整数写入单元格 i 正在 A_i,所以答案是 3.
示例输入 2
10 1 1 1 1 1 0 1 1 1 0
示例输出 2
9