P12442 [NERC2023] Kim's Quest

在康比纳托里亚古老学院被遗忘的大厅里，一位名叫金姆的天才数学家面临着一个不寻常的挑战。他们发现了一个古老的整数序列，据信这是来自传奇的康比纳托里亚神谕的加密信息，金姆想要破译其中隐藏的含义。 金姆的任务是在序列中寻找特定的模式，这些模式被称为**和谐子序列**。这些特殊的子序列需要满足每三个连续数字之和为偶数，且每个子序列的长度必须至少为三个数字。 给定一个长度为 $n$ 的序列 $a_i$（$1 \le i \le n$），其长度为 $m$ 的**子序列**定义为 $a_{b_1}, a_{b_2}, \ldots, a_{b_m}$，由一组 $m$ 个索引 $b_j$ 唯一确定，其中 $1 \le b_1 < b_2 < \ldots < b_m \le n$。由不同索引集 $b_j$ 给出的子序列被视为不同的子序列。 金姆的探索有一个转折：这些和谐子序列的数量可能非常庞大。为了有效地报告发现结果，金姆必须计算这些子序列的总数，并将答案对 $998\,244\,353$ 取模后输出。

第一行包含一个整数 $n$ —— 序列的长度（$3 \le n \le 2 \cdot 10^5$）。 第二行包含 $n$ 个用空格分隔的整数 $a_i$ —— 序列的元素（$1 \le a_i \le 2 \cdot 10^5$）。

输出一个数字 —— 和谐子序列的数量，对 $998\,244\,353$ 取模后的结果。

在第五个样例的输入数据中，数字序列被分成三行以提高可读性，但在实际的测试数据中，序列是以一行给出的。在这个例子中，实际的和谐子序列数量为 $4\,991\,221\,765 = 5 \times 998\,244\,353$，因此输出为零，因为这是其对 $998\,244\,353$ 取模后的结果。 翻译由 DeepSeek V3 完成