問題一覧 > 通常問題

No.2898 Update Max

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
1 ProblemId : 11387 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-19 21:49:31

問題文

長さが $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$
よって答えは $4 + 2 = 6$ です。

サンプル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$ です。
よって答えは $4$ です。

サンプル3
入力
17
-1 -1 8 2 10 9 12 -1 7 -1 -1 -1 11 -1 13 -1 -1
出力
1310400

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。