Mirror and Order

AtCoder

IDarc188_d

Time2000ms

Memory256MB

Difficulty—

You are going to create $N$ sequences of length $3$, satisfying the following conditions. * For each of $k = 1,2,3$, the following holds: * Among the $k$\-th elements of the sequences, each integer from $1$ through $N$ appears exactly once. For this sequence of sequences, define sequences $a=(a_1,a_2,\ldots,a_N)$ and $b=(b_1,b_2,\ldots,b_N)$ as follows. * Let $s_i$ be the $i$\-th sequence, and let $t_i$ be the reverse of the $i$\-th sequence. When all of these are sorted in lexicographical order, $s_i$ comes $a_i$\-th, and $t_i$ comes $b_i$\-th. * Here, if there are identical sequences among the $2N$ sequences, $a$ and $b$ are not defined. Therefore, if $a$ and $b$ are defined, each integer from $1$ through $2N$ appears exactly once in the concatenation of $a$ and $b$. You are given sequences $A$ and $B$ of length $N$, where each element of $A$ is an integer between $1$ and $2N$, and each element of $B$ is either an integer between $1$ and $2N$ or $-1$. Also, in the concatenation of $A$ and $B$, each integer other than $-1$ appears at most once. How many pairs of sequences $a,b$ are there such that $a$ and $b$ are defined and the following holds for each integer $i$ from $1$ through $N$? * $a_i = A_i$. * $b_i = B_i$ if $B_i \neq -1$. Find the count modulo $998244353$. ## Constraints * $2 \leq N \leq 3000$ * $1 \leq A_i \leq 2N$ * $1 \leq B_i \leq 2N$ or $B_i = -1$. * In the concatenation of $A$ and $B$, each integer other than $-1$ appears at most once. That is, * $A_i \neq A_j$ if $i \neq j$. * $B_i \neq B_j$ if $i \neq j$ and $B_i,B_j \neq -1$. * $A_i \neq B_j$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$ [samples]

Samples

Input #1

3
2 3 6
-1 1 -1

Output #1

1

For example, consider creating the following three sequences:

1.  $(1,2,3)$
2.  $(2,1,1)$
3.  $(3,3,2)$

In this case, when sorting $s_i$ and $t_i$ lexicographically, we have:

> $t_2 = (1,1,2) < s_1 = (1,2,3) < s_2 = (2,1,1) < t_3 = (2,3,3) < t_1 = (3,2,1) < s_3 = (3,3,2)$

Thus, $(a_1,a_2,a_3,b_1,b_2,b_3) = (2,3,6,5,1,4)$. Here, $a$ matches the given $A$, and the second element of $b$ also matches that of $B$, so this is one pair of sequences $a,b$ satisfying the conditions.
On the other hand, if we create the following three sequences, $s_1$ and $t_1$ become identical, so $a$ and $b$ are not defined.

1.  $(1,2,1)$
2.  $(2,1,3)$
3.  $(3,3,2)$

In fact, $a=(2,3,6), b=(5,1,4)$ is the only pair of sequences satisfying the conditions.

Input #2

15
5 16 1 12 30 20 4 13 9 8 24 21 26 28 17
-1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 29 -1 -1 -1

Output #2

758094847

Print the count modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Mirror and Order",
    "description": {
      "content": "You are going to create $N$ sequences of length $3$, satisfying the following conditions. *   For each of $k = 1,2,3$, the following holds:     *   Among the $k$\\-th elements of the sequences, each i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc188_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are going to create $N$ sequences of length $3$, satisfying the following conditions.\n\n*   For each of $k = 1,2,3$, the following holds:\n    *   Among the $k$\\-th elements of the sequences, each i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments