[2018 年湖南省队集训] Gift

题目描述

小皮刚认识了一个可爱的女孩子小 S。快到她的生日了，小皮决定买两个排列 $A,B$，一个留给自己，一个送给她。

定义两个长度为 $n$ 的排列 $A,B$ 的相似度为：将排列 $A$ 通过若干次操作变成排列 $B$ 所需要的最少操作次数。

每次操作可以交换排列中的任意两个元素。

现在给定两个长度为 $n$ 的序列 $A,B$，其中一些位置的值为 $0$。你需要分别补全两个序列中的所有 $0$，使得 $A$ 和 $B$ 都成为 $1\sim n$ 的排列。

对于每一个 $i\in[0,n-1]$，求有多少种补全方案，使得补全后的两个排列 $A,B$ 的相似度恰好为 $i$。

由于答案可能很大，请将所有答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$，表示序列长度。

第二行输入 $n$ 个整数 $A_1,A_2,\ldots,A_n$。

第三行输入 $n$ 个整数 $B_1,B_2,\ldots,B_n$。

其中，值为 $0$ 的位置表示尚未确定，需要进行补全。

数据保证，在序列 $A$ 和序列 $B$ 中，除 $0$ 以外的元素分别互不相同。

输出格式

输出一行 $n$ 个整数。

第 $i$ 个整数表示：补全后两个排列的相似度恰好为 $i-1$ 的方案数，对 $998244353$ 取模后的结果。

注意：原题面曾误写为“输出 $n$ 行”。根据官方数据及标程，正确格式为一行输出 $n$ 个整数。

样例 1

3
1 0 0
0 2 0

1 2 1

样例 2

4
1 0 0 3
0 0 0 4

0 2 6 4

数据范围

特殊性质：

1. 对任意 $i\in[1,n]$，均有 $A_i>0$ 且 $B_i>0$；
2. 对任意 $i\in[1,n]$，均有 $A_i=B_i=0$。

对于全部数据，$n\le 2000$。

时间与空间限制

• 时间限制：$1\text{s}$
• 空间限制：$256\text{MB}$