Official Analysis (C++)

Explanation

First, we should try to figure out what a good sequence generally looks like. As mentioned in the problem, a good sequence must have its median equal its mex. With that definition, we can make the following observations.

1. Our subarrays must be of even length
2. The two median values of our subarray must be an even distance apart

With those out of the way, we can make a few more observations. The first is that elements $1, 2, 3 \cdots \frac{\text{len}}{2}$ must be present in our subarray. If this wasn't the case, our mex would be less than $\frac{\text{len}}{2}$, which means it cannot be equal to the median of our subarray.

Our next observation is an improvement upon the second observation. The distance between our two median values must be equal to $2$. If this was not the case, our mex would be less than our median.

With those observations, we can calculate our answer with some combinatorics. The easiest way to do this is to iterate on our subarray length and count the number of good subarrays. Then, we can count the number of ways to fill in the elements around our subarrays. This works because each subarray length maps to one median/mex value, allowing us to calculate our final answers.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>

using ll = long long;

constexpr int MOD = 998244353;

 Code Snippet: Modular Exponentiation (from the module) (Click to expand)

namespace Combo {
std::vector<ll> fact;