No.2815 Smaller than all
タグ : / 解いたユーザー数 21
作問者 :
Magentor
/ テスター :
hirayuu_yc
highlighter
keisuke6
Yoyoyo8128
fact493
zeta7532
warabi0906
問題文
長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。ここで、以下の問題を考えます。
整数列正整数列 (21:53修正) $S$ が与えられる。長さ $N$ の正整数列 $T$ であって以下の条件を満たすもののうち辞書順最大のものを求めよ。辞書順最大の $T$ は必ず存在することが示せる。 (22:00追記)
- 正整数列 $T$ の全ての長さ $|S|$ の（連続とは限らない）部分列が、辞書順で $S$ 以下である。
上の問題の答えが $A=(A_1,A_2,\dots,A_N)$ と等しくなるような長さ $1$ 以上 $N$ 以下の正整数列 $S$ の個数を $998244353$ で割った余りを求めてください。
ただし、整数列の部分列とは、その整数列から $0$ 個以上の要素を削除して、残った要素を順序を変えずに並べた整数列を指します。
数列の辞書順とは？
$A=(A_1,A_2,\dots,A_{|A|})$ が辞書順で $B=(B_1,B_2,\dots,B_{|B|})$ 以下であるとは、以下の $2$ つのうちどちらかが成り立つことを言います。ここで、$|A|,|B|$ はそれぞれ $A,B$ の長さを表します。
- $|A| \leq |B|$ かつ $(A_1,A_2,\dots,A_{|A|})=(B_1,B_2,\dots,B_{|A|})$ である。
- ある整数 $1 \leq i \leq \min(|A|,|B|)$ が存在して、以下の $2$ つが成り立つ。
- $(A_1,A_2,\dots,A_{i-1})=(B_1,B_2,\dots,B_{i-1})$
- $A_i<B_i$
制約
- 入力は全て整数である
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq10^9$
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1\ A_2\ \dots\ A_N$
出力
答えを $1$ 行に出力せよ。
サンプル
サンプル1
入力
3 1 1 2
出力
2
$S=(1,1,2),(1,2)$ の場合のみ条件を満たすことが証明できます。例えば $S=(1,2)$ の場合、$(1,1,2)$ の部分列として考えられるものは $(1,1),(1,2),(1,2)$ となりますが、これらは全て辞書順で $(1,2)$ 以下です。また、$(1,1,2)$ の場合に辞書順最大となることが確認できるので、$(1,2)$ は条件を満たします。
サンプル2
入力
5 1 1 1 1 1
出力
5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。