蓝桥杯2026年第十七届省赛真题-奇偶交换

给定一个长度为 N 的初始序列，序列中的每个数字均在 {0, 1, 2, 3} 范围内。

你可以对该序列进行任意次数的交换操作，每次操作的规则如下：在序列中选择两个相邻的数字，若这两个数字相加的结果为奇数，则可以交换它们的位置。

现在，请你计算通过这些合法的交换操作，总共能得到多少种不同的数字序列？注意：两个序列被视为是不同的，当且仅当它们在至少一个位置上的数字不同。由于最终的结果可能非常大，请将其对 998244353 取模后输出。

第一行包含一个正整数 N，表示序列的长度。

第二行包含 N 个整数 P1, P2,. . . , PN，代表初始的数字序列。每个数字均在{0, 1, 2, 3} 范围内。

输出 一 行，包 含 一 个 整 数，表 示 可 能 产 生 的 不 同 序 列 的 总 数，结 果 对998244353 取模。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ N ≤ 1000；

对于所有评测用例，1 ≤ N ≤ 10⁵，所有输入的数字 Pi ∈{0, 1, 2, 3}。