CF1912K Kim's Quest

在 Kombinatoria 古老学院被遗忘的大厅里，一位天才数学家 Kim 面临着一个不同寻常的挑战。他发现了一串古老的整数序列，据说这是传奇的 Kombinatoria 神谕者留下的神秘信息，Kim 希望解读其中隐藏的含义。 Kim 的任务是要在序列中找到特定的模式，被称为“和谐子序列”。这些子序列有一个特殊的性质：每连续三个数的和都是偶数，并且每个子序列的长度至少为三。 给定一个长度为 $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$ 得到的子序列被认为是不同的。 Kim 的任务还有一个难点：这些和谐子序列的数量可能非常庞大。为了有效地报告结果，Kim 需要计算这些子序列的总数，并将答案对 $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$ 取余的结果为零。 由 ChatGPT 4.1 翻译