No.1709 Indistinguishable by MEX
タグ : / 解いたユーザー数 137
作問者 :
chineristAC
/ テスター :
👑 
hitonanode
unti
Problem Statement
Let $\mathrm{mex}(x_1,\ x_2,\ \dots,\ x_k)$ denote the smallest non-negative integer not contained in $x_1,\ x_2,\ \dots,\ x_k$.
You are given a permutation $P=(P_1,\ P_2,\ \dots,\ P_N)$ of length $N$ consisting of the integers from $0$ to $N-1$.
Find the number, modulo $998244353$, of permutations $Q$ consisting of the integers from $0$ to $N-1$ that satisfy the following condition.
Condition- For every pair of integers $1 \le l \le r \le N$, $\mathrm{mex}(P_l,\ P_{l+1},\ \dots,\ P_r)=\mathrm{mex}(Q_l,\ Q_{l+1},\ \dots,\ Q_r)$ holds.
Input
$N$ $P_1$ $P_2$ $\dots$ $P_N$
- $1 \le N \le 2 \times 10^5$
- $0 \le P_i \le N-1$
- If $i\neq j$, then $P_i \neq P_j$
- All input values are integers
Output
Print the answer.
End the output with a newline.
Sample
Sample 1
Input
4 1 3 2 0
Output
2
If $Q=(1,\ 2,\ 3,\ 0)$, then for example $\mathrm{mex}(P_2,\ P_3,\ P_4)=\mathrm{mex}(Q_2,\ Q_3,\ Q_4)=1$.
For the other $l,\ r$ as well, $\mathrm{mex}(P_l,\ P_{l+1},\ \dots,\ P_r)=\mathrm{mex}(Q_l,\ Q_{l+1},\ \dots,\ Q_r)$ holds, so $Q$ satisfies the condition.
The permutations satisfying the condition are this $Q$ and $P$ itself, for a total of $2$.
Sample 2
Input
6 3 4 0 2 1 5
Output
1
Sample 3
Input
20 6 10 8 4 14 3 19 0 13 16 2 12 17 9 15 18 11 5 1 7
Output
781469644
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。