← 返回题目列表

Codeforces · 715/E

E. 完成排列

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

ZS 编码器被给予 {1, 2, ..., n} 的两个排列 p 和 q,但其中一些元素被替换为 0。两个排列 p 和 q 之间的距离定义为将 p 变成 q 所需的最小移动次数。一次移动就是交换 p 的 2 个元素。

ZS 编码器想要确定用集合 {1, 2, ..., n} 中的正整数替换零的方法数量,使得 p 和 q 是 {1, 2, ..., n} 的排列,并且 p 和 q 之间的距离恰好为 k。

编码员 ZS 想要找到所有 0 ≤ k ≤ n - 1 的答案。你能帮助他吗?

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 250) — 排列中的元素数量。

第二行包含 n 个整数,p1, p2, ..., pn (0 ≤ pi ≤ n) - 排列 p。保证至少有一种方法来替换零,使得 p 是 {1, 2, ..., n} 的排列。

第三行包含 n 个整数 q1, q2, ..., qn (0 ≤ qi ≤ n) - 排列 q。保证至少有一种方法来替换零,使得 q 是 {1, 2, ..., n} 的排列。

输出

打印 n 个整数,其中第 i 个应该表示 k = i - 1 的答案。由于答案可能很大,而且编码员 ZS 喜欢奇怪的素数,所以打印它们对 998244353 = 223·7·17 + 1 取模,这是一个素数。

示例

输入 #1

3
1 0 0
0 2 0

输出 #1

1 2 1

输入 #2

4
1 0 0 3
0 0 0 4

输出 #2

0 2 6 4

输入 #3

6
1 3 2 5 4 6
6 4 5 1 0 0

输出 #3

0 0 0 0 1 1

输入#4

4
1 2 3 4
2 3 4 1

输出#4

0 0 0 1

注意

在第一个示例案例中,只有一种方法可以替换零,从而需要 0 次交换才能将 p 转换为 q,即 p = (1, 2, 3),q = (1, 2, 3)。

有两种方法可以替换零,以便需要 1 次交换才能将 p 变成 q。其中一种方法是 p = (1, 2, 3), q = (3, 2, 1),然后交换 p 中的 1 和 3 将其变换为 q。另一种方式是 p = (1, 3, 2),q = (1, 2, 3)。在这种情况下,交换 2 和 3 就可以了。

最后,有一种方法可以替换零,这样需要2次交换才能将p变成q,即p = (1, 3, 2),q = (3, 2, 1)。然后,我们可以将 p 转换为 q,如下所示:$$(1,3,2)\to(2,3,1)\to(3,2,1)$$。