Non-Descending Arrays

We need count subsets of indices. Choosing a subset is the same thing as choosing, for every index $i$, whether to swap $(a_i,b_i)$ or not.

So define two possible states for each position:

• state $0$: do not swap, so the pair is $(a_i,b_i)$
• state $1$: swap, so the pair is $(b_i,a_i)$

After all choices, the first chosen values must form a non-descending array, and the second chosen values must also form a non-descending array.

The Key Local Fact

Non-descending order is checked between neighbors. That means if the prefix up to $i-1$ is already valid, then adding position $i$ only needs one check against position $i-1$.

For a state $s$ at index $i$, let:

$$X(i,s)=\begin{cases} a_i & s=0\\ b_i & s=1\end{cases}$$

and

$$Y(i,s)=\begin{cases} b_i & s=0\\ a_i & s=1\end{cases}$$

A previous state $p$ at index $i-1$ can transition into current state $s$ at index $i$ iff:

$$X(i-1,p) \le X(i,s)$$

and

$$Y(i-1,p) \le Y(i,s)$$

Both arrays have to behave. One failing inequality kills the transition. Brutal, but fair.

DP Definition

Let $dp[i][s]$ be the number of valid choices for the prefix $1 \ldots i$, where index $i$ is in state $s$.

Base case:

$$dp[1][0]=1, \quad dp[1][1]=1$$

Why both? Because choosing no swap and choosing swap are different subsets. Even if $a_1=b_1$ and the final arrays look identical, the subsets are still different. The sample with $n=1$ makes this very clear.

Transition:

$$dp[i][s] = \sum_{p\in\{0,1\}} dp[i-1][p]$$

over only the states $p$ where the transition $p \to s$ is valid.

Since there are only $2$ previous states and $2$ current states, each position takes constant time.

Answer

After processing all positions, the answer is:

$$dp[n][0]+dp[n][1]$$

modulo $998244353$.

Complexity

For each adjacent pair, we try $4$ transitions. So the runtime is:

$$O(n)$$

per test case, with $O(1)$ memory if we keep only the previous DP row.