問題一覧 > 通常問題

No.2898 Update Max

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

問題文

長さが NN の順列 P=(P1,P2,⋯ ,PN)P = \left( P_1, P_2, \cdots, P_N \right) に対して、 f(P)f \left( P \right) を以下のように定義します。

  • 1≤i≤N1 \leq i \leq N を満たす整数 ii のうち、 max⁡(P1,P2,⋯ ,Pi)=Pi\max \left( P_1, P_2, \cdots, P_i \right) = P_i であるような個数。

長さが NN の整数列 A=(A1,A2,⋯ ,AN)A = \left( A_1, A_2, \cdots, A_N \right) が与えられます。ここで、 Ai=−1A_i = -1 または 1≤Ai≤N1 \leq A_i \leq N が成立します。

長さが NN の順列 P=(P1,P2,⋯ ,PN)P = \left( P_1, P_2, \cdots, P_N \right) であって、 1≤i≤N1 \leq i \leq N について Ai=−1A_i = -1 または Ai=PiA_i = P_i を満たすようなものを よい順列 とします。 よい順列 すべてに対して f(P)f(P) を足し合わせた値を 998244353998244353 で割ったあまりを求めてください。

入力

NN
A1  A2  ⋯ANA_1\ \ A_2\ \ \cdots A_N

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • Ai=−1A_i = -1 または 1≤Ai≤N1 \leq A_i \leq N
  • 1≤i<j≤N1 \leq i < j \leq N かつ Ai≠−1A_i \neq -1 かつ Aj≠−1A_j \neq -1 ならば Ai≠AjA_i \neq A_j
  • 入力はすべて整数

出力

最後に改行してください。

サンプル

サンプル1
入力
4
1 -1 3 -1
出力
6

よい順列 は P=(1,2,3,4)P = \left( 1, 2, 3, 4 \right) と P=(1,4,3,2)P = \left( 1, 4, 3, 2 \right) の 22 つです。

  • P=(1,2,3,4)P = \left( 1, 2, 3, 4 \right) のとき f(P)=4f \left( P \right) = 4 です。これは以下より分かります。
    • max⁡(P1)=1=P1\max \left( P_1 \right) = 1 = P_1
    • max⁡(P1,P2)=2=P2\max \left( P_1, P_2 \right) = 2 = P_2
    • max⁡(P1,P2,P3)=3=P3\max \left( P_1, P_2, P_3 \right) = 3 = P_3
    • max⁡(P1,P2,P3,P4)=4=P4\max \left( P_1, P_2, P_3, P_4 \right) = 4 = P_4
  • P=(1,4,3,2)P = \left( 1, 4, 3, 2 \right) のとき f(P)=2f \left( P \right) = 2 です。これは以下より分かります。
    • max⁡(P1)=1=P1\max \left( P_1 \right) = 1 = P_1
    • max⁡(P1,P2)=4=P2\max \left( P_1, P_2 \right) = 4 = P_2
    • max⁡(P1,P2,P3)=4≠P3\max \left( P_1, P_2, P_3 \right) = 4 \neq P_3
    • max⁡(P1,P2,P3,P4)=4≠P4\max \left( P_1, P_2, P_3, P_4 \right) = 4 \neq P_4
よって答えは 4+2=64 + 2 = 6 です。

サンプル2
入力
6
2 4 5 3 6 1
出力
4

よい順列 は P=(2,4,5,3,6,1)P = \left( 2, 4, 5, 3, 6, 1 \right) の 11 つです。

  • P=(2,4,5,3,6,1)P = \left( 2, 4, 5, 3, 6, 1 \right) のとき f(P)=4f \left( P \right) = 4 です。
よって答えは 44 です。

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

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