問題一覧 > 通常問題

No.2898 Update Max

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 43
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 11387 / 自分の提出
問題文最終更新日: 2024-09-19 21:49:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 447 オムニバス (順位表) の他の問題:

Problem Statement

For a permutation $P = \left( P_1, P_2, \cdots, P_N \right)$ of length $N$, define $f \left( P \right)$ as follows.

  • The number of integers $i$ satisfying $1 \leq i \leq N$ such that $\max \left( P_1, P_2, \cdots, P_i \right) = P_i$.

You are given an integer sequence $A = \left( A_1, A_2, \cdots, A_N \right)$ of length $N$. Here, $A_i = -1$ or $1 \leq A_i \leq N$ holds.

A permutation $P = \left( P_1, P_2, \cdots, P_N \right)$ of length $N$ is called a good permutation if $A_i = -1$ or $A_i = P_i$ holds for $1 \leq i \leq N$. Find the sum of $f(P)$ over all good permutations, modulo $998244353$.

Input

$N$
$A_1\ \ A_2\ \ \cdots A_N$

  • $1 \leq N \leq 2 \times 10^5$
  • $A_i = -1$ or $1 \leq A_i \leq N$
  • If $1 \leq i < j \leq N$ and $A_i \neq -1$ and $A_j \neq -1$, then $A_i \neq A_j$
  • All input values are integers

Output

Print a newline at the end.

Sample

Sample 1
Input
4
1 -1 3 -1
Output
6

There are $2$ good permutations: $P = \left( 1, 2, 3, 4 \right)$ and $P = \left( 1, 4, 3, 2 \right)$.

  • When $P = \left( 1, 2, 3, 4 \right)$, $f \left( P \right) = 4$. This can be seen from the following.
    • $\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$
  • When $P = \left( 1, 4, 3, 2 \right)$, $f \left( P \right) = 2$. This can be seen from the following.
    • $\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$
Therefore, the answer is $4 + 2 = 6$.

Sample 2
Input
6
2 4 5 3 6 1
Output
4

There is $1$ good permutation: $P = \left( 2, 4, 5, 3, 6, 1 \right)$.

  • When $P = \left( 2, 4, 5, 3, 6, 1 \right)$, $f \left( P \right) = 4$.
Therefore, the answer is $4$.

Sample 3
Input
17
-1 -1 8 2 10 9 12 -1 7 -1 -1 -1 11 -1 13 -1 -1
Output
1310400

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