题意：给定一个长度为 n 的序列，求有多少个子序列满足该子序列内任意相邻 3 个数的和为偶数。
只与奇偶有关，所以可以把状态转化为 01 的。
设 \(f[i][x][y]\) 表示在前 i 个数中，最后一位为 x，倒数第二位为 y 的方案数。
$ w(a[i]) $ 为以 a[i] 结尾的方案数。
\[w(a[i]) = \sum f[i - 1][y][z] \ \ \ \ (a[i] + y + z) \% 2 == 0 \]最后需要把 \([a[i], y]\) 的对数加入 \(f[i][a[i]][y]\)，以此更新下个数。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
#define pb emplace_back
#define All(X) X.begin(), X.end()
using namespace std;
using ll = long long;
constexpr ll P = 998244353;
int n, f[200005][2][2], cnt[2];
int ans;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
rep(i, 1, n) {
int x; cin >> x;
x &= 1;
rep(y, 0, 1) rep(z, 0, 1) if((x + y + z) % 2 == 0) {
f[i][x][y] = (f[i][x][y] + f[i - 1][y][z]) % P;
ans = (ans + f[i - 1][y][z]) % P; // 以 a[i] 结尾的方案的贡献
}
rep(y, 0, 1) rep(z, 0, 1) f[i][y][z] = (f[i][y][z] + f[i - 1][y][z]) % P; // 前缀和为前i个数的方案
rep(y, 0, 1) f[i][x][y] = (f[i][x][y] + cnt[y]) % P; // 统计 [x, y] 二元组的个数，由此更新 i + 1
++ cnt[x];
}
cout << ans;
return 0;
}