問題一覧 > 通常問題

No.3052 Increasing Sliding Window Minimum

レベル : / AI推定難易度 : 2475 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : suisen / テスター : 👑 hamamu 👑 rin204
お気に入りにしたユーザー ProblemId : 10653 / 自分の提出
問題文最終更新日: 2025-01-25 15:04:22
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 459 (順位表) の他の問題:

Problem Statement

You are given an integer $n$ greater than or equal to $2$ and an integer sequence $A=(A_1,A_2,\ldots,A_n)$ of length $n$. Here, for all $i=1,2,\ldots,n$, either $A_i=-1$ or $1\leq A_i\leq n$ holds.

Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\ldots,P_n)$ of $(1,2,\ldots,n)$ that satisfy all of the following conditions.

  • For every integer $i$ between $1$ and $n$, inclusive, if $A_i\neq -1$, then $P_i=A_i$.
  • For every integer $i$ between $1$ and $n-2$, inclusive, $\min(P_i,P_{i+1})\leq \min(P_{i+1},P_{i+2})$.

You are given $T$ test cases in 1 file; solve the above problem for all of them.

Input

The input is given from standard input in the following format.

$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$

Here, $\mathrm{testcase}_i$ represents the $i$-th test case and is given in the following format.

$n$
$A_1$ $A_2$ $\cdots$ $A_n$
  • All input values are integers.
  • $1\leq T\leq 5000$
  • $2\leq n\leq 5000$
  • $A_i=-1$ or $1\leq A_i\leq n$
  • For $i,j$ such that $i\neq j$, if $A_i\neq -1, A_j\neq-1$, then $A_i\neq A_j$.
  • The sum of $n$ over the $T$ test cases is at most $5000$.

Output

Output $T$ lines. On the $i\ (1\leq i\leq T)$-th line, output the answer for the $i$-th test case. Also output a newline after the $T$-th line.

Sample

Sample 1
Input
4
3
-1 2 -1
5
3 -1 2 -1 -1
5
5 4 3 2 1
20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Output
1
2
0
799043977
  • Regarding the 1st test case
    This input represents $n=3,\ A=(-1,2,-1)$.

    $P=(1,2,3)$ is the only permutation that satisfies the conditions. Therefore, output $1$ as the answer.

    $P=(3,2,1)$ satisfies the 1st condition, but it does not satisfy the 2nd condition because $\min(P_1,P_2)=2\gt \min(P_2,P_3)=1$.

    $P=(2,1,3)$ satisfies the 2nd condition, but it does not satisfy the 1st condition because $A_2\neq -1$ and $P_2\neq A_2$.

  • Regarding the 3rd test case
    There may be no permutation $P$ that satisfies the conditions.

  • Regarding the 4th test case
    Note that you must output the remainder modulo $998244353$.

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