← 返回题目列表

AtCoder · arc188_d

D. 镜子与秩序

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

您将创建 N 长度序列 3,满足以下条件。

  • 对于每个 k = 1,2,3,以下成立:
    • 其中 k- 序列的第一个元素,每个整数来自 1 通过 N 只出现一次。

对于这个序列序列,定义序列 a=(a_1,a_2,\ldots,a_N) 和 b=(b_1,b_2,\ldots,b_N) 如下。

  • 让 s_i 是 i第一个序列,并让 t_i 是相反的 i第一个序列。当所有这些都按字典顺序排序时, s_i 来了 a_i-th,以及 t_i 来了 b_i-th。
  • 这里,如果存在相同的序列 2N 序列, a 和 b 未定义。

因此,如果 a 和 b 被定义,每个整数来自 1 通过 2N 在串联中恰好出现一次 a 和 b.

给定了序列 A 和 B 长度 N,其中每个元素 A 是介于 1 和 2N,以及每个元素 B 是介于 1 和 2N or -1。 另外,在串联中 A 和 B,除 -1 最多出现一次。

有多少对序列 a,b 有这样的吗 a 和 b 被定义并且以下对于每个整数成立 i 来自 1 通过 N?

  • a_i = A_i.
  • b_i = B_i if B_i \neq -1.

求计数模数 998244353.

约束

  • 2 \leq N \leq 3000
  • 1 \leq A_i \leq 2N
  • 1 \leq B_i \leq 2N or B_i = -1.
  • 在串联中 A 和 B,除 -1 最多出现一次。也就是说,
    • A_i \neq A_j if i \neq j.
    • B_i \neq B_j if i \neq j 和 B_i,B_j \neq -1.
    • A_i \neq B_j.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

输出

打印计数模数 998244353.


示例输入 1

3
2 3 6
-1 1 -1

示例输出 1

1

例如,考虑创建以下三个序列:

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

在这种情况下,排序时 s_i 和 t_i 按字典顺序,我们有:

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)

因此, (a_1,a_2,a_3,b_1,b_2,b_3) = (2,3,6,5,1,4)。在这里, 交换后 a 与给定的匹配 A,第二个元素 b 也匹配 B,所以这是一对序列 a,b 满足条件。

另一方面,如果我们创建以下三个序列, s_1 和 t_1 变得相同,所以 a 和 b 未定义。

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

事实上, a=(2,3,6), b=(5,1,4) 是唯一满足条件的序列对。


示例输入 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

示例输出 2

758094847

打印计数模数 998244353.