No.3052 Increasing Sliding Window Minimum
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu