No.2898 Update Max
タグ : / 解いたユーザー数 40
作問者 :
蜜蜂
/ テスター :
Mitarushi
問題文
長さが $N$ の順列 $P = \left( P_1, P_2, \cdots, P_N \right)$ に対して、 $f \left( P \right)$ を以下のように定義します。
- $1 \leq i \leq N$ を満たす整数 $i$ のうち、 $\max \left( P_1, P_2, \cdots, P_i \right) = P_i$ であるような個数。
長さが $N$ の整数列 $A = \left( A_1, A_2, \cdots, A_N \right)$ が与えられます。ここで、 $A_i = -1$ または $1 \leq A_i \leq N$ が成立します。
長さが $N$ の順列 $P = \left( P_1, P_2, \cdots, P_N \right)$ であって、 $1 \leq i \leq N$ について $A_i = -1$ または $A_i = P_i$ を満たすようなものを よい順列 とします。
よい順列 すべてに対して $f(P)$ を足し合わせた値を $998244353$ で割ったあまりを求めてください。
入力
$N$
$A_1\ \ A_2\ \ \cdots A_N$
- $1 \leq N \leq 2 \times 10^5$
- $A_i = -1$ または $1 \leq A_i \leq N$
- $1 \leq i < j \leq N$ かつ $A_i \neq -1$ かつ $A_j \neq -1$ ならば $A_i \neq A_j$
- 入力はすべて整数
出力
最後に改行してください。
サンプル
サンプル1
入力
4
1 -1 3 -1
出力
6
よい順列 は $P = \left( 1, 2, 3, 4 \right)$ と $P = \left( 1, 4, 3, 2 \right)$ の $2$ つです。
- $P = \left( 1, 2, 3, 4 \right)$ のとき $f \left( P \right) = 4$ です。これは以下より分かります。
- $\max \left( P_1 \right) = 1 = P_1$
- $\max \left( P_1, P_2 \right) = 2 = P_2$
- $\max \left( P_1, P_2, P_3 \right) = 3 = P_3$
- $\max \left( P_1, P_2, P_3, P_4 \right) = 4 = P_4$
- $P = \left( 1, 4, 3, 2 \right)$ のとき $f \left( P \right) = 2$ です。これは以下より分かります。
- $\max \left( P_1 \right) = 1 = P_1$
- $\max \left( P_1, P_2 \right) = 4 = P_2$
- $\max \left( P_1, P_2, P_3 \right) = 4 \neq P_3$
- $\max \left( P_1, P_2, P_3, P_4 \right) = 4 \neq P_4$
サンプル2
入力
6
2 4 5 3 6 1
出力
4
よい順列 は $P = \left( 2, 4, 5, 3, 6, 1 \right)$ の $1$ つです。
- $P = \left( 2, 4, 5, 3, 6, 1 \right)$ のとき $f \left( P \right) = 4$ です。
サンプル3
入力
17
-1 -1 8 2 10 9 12 -1 7 -1 -1 -1 11 -1 13 -1 -1
出力
1310400
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。