No.1709 Indistinguishable by MEX
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 129
作問者 :
chineristAC
/ テスター :
hitonanode
unti
タグ : / 解いたユーザー数 129
作問者 :
chineristAC
/ テスター :
hitonanode
unti
問題文最終更新日: 2021-10-09 02:48:28
問題文
$\mathrm{mex}(x_1,\ x_2,\ \dots,\ x_k)$ で $x_1,\ x_2,\ \dots,\ x_k$ に含まれない最小の非負整数を表すものとします。
長さ $N$ で $0$ から $N-1$ までの整数からなる順列 $P=(P_1,\ P_2,\ \dots,\ P_N)$ が与えられます。
以下の条件を満たす、$0$ から $N-1$ までの整数からなる順列 $Q$ の個数を $998244353$ で割った余りを求めてください。
条件- 任意の整数の組 $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)$ が成り立つ。
入力
$N$ $P_1$ $P_2$ $\dots$ $P_N$
- $1 \le N \le 2 \times 10^5$
- $0 \le P_i \le N-1$
- $i\neq j$ ならば $P_i \neq P_j$
- 与えられる入力はすべて整数
出力
答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
4 1 3 2 0
出力
2
$Q=(1,\ 2,\ 3,\ 0)$ とすると例えば $\mathrm{mex}(P_2,\ P_3,\ P_4)=\mathrm{mex}(Q_2,\ Q_3,\ Q_4)=1$ です。
このほかの $l,\ r$ についても $\mathrm{mex}(P_l,\ P_{l+1},\ \dots,\ P_r)=\mathrm{mex}(Q_l,\ Q_{l+1},\ \dots,\ Q_r)$ が成り立つので $Q$ は条件を満たします。
条件を満たすのはこの $Q$ と $P$ 自身の $2$ 通りです。
サンプル2
入力
6 3 4 0 2 1 5
出力
1
サンプル3
入力
20 6 10 8 4 14 3 19 0 13 16 2 12 17 9 15 18 11 5 1 7
出力
781469644
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。