English · Original
Chinese · Translation
Formal · Original
ZS the Coder is given two permutations _p_ and _q_ of {1, 2, ..., _n_}, but some of their elements are replaced with 0. The _distance_ between two permutations _p_ and _q_ is defined as the minimum number of moves required to turn _p_ into _q_. A move consists of swapping exactly 2 elements of _p_.
ZS the Coder wants to determine the number of ways to replace the zeros with positive integers from the set {1, 2, ..., _n_} such that _p_ and _q_ are permutations of {1, 2, ..., _n_} and the distance between _p_ and _q_ is exactly _k_.
ZS the Coder wants to find the answer for all 0 ≤ _k_ ≤ _n_ - 1. Can you help him?
## Input
The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 250) — the number of elements in the permutations.
The second line contains _n_ integers, _p_1, _p_2, ..., _p__n_ (0 ≤ _p__i_ ≤ _n_) — the permutation _p_. It is guaranteed that there is at least one way to replace zeros such that _p_ is a permutation of {1, 2, ..., _n_}.
The third line contains _n_ integers, _q_1, _q_2, ..., _q__n_ (0 ≤ _q__i_ ≤ _n_) — the permutation _q_. It is guaranteed that there is at least one way to replace zeros such that _q_ is a permutation of {1, 2, ..., _n_}.
## Output
Print _n_ integers, _i_\-th of them should denote the answer for _k_ = _i_ - 1. Since the answer may be quite large, and ZS the Coder loves weird primes, print them modulo 998244353 = 223·7·17 + 1, which is a prime.
[samples]
## Note
In the first sample case, there is the only way to replace zeros so that it takes 0 swaps to convert _p_ into _q_, namely _p_ = (1, 2, 3), _q_ = (1, 2, 3).
There are two ways to replace zeros so that it takes 1 swap to turn _p_ into _q_. One of these ways is _p_ = (1, 2, 3), _q_ = (3, 2, 1), then swapping 1 and 3 from _p_ transform it into _q_. The other way is _p_ = (1, 3, 2), _q_ = (1, 2, 3). Swapping 2 and 3 works in this case.
Finally, there is one way to replace zeros so that it takes 2 swaps to turn _p_ into _q_, namely _p_ = (1, 3, 2), _q_ = (3, 2, 1). Then, we can transform _p_ into _q_ like following: .
ZS the Coder 被给定两个排列 #cf_span[p] 和 #cf_span[q]，它们都是 #cf_span[{1, 2, ..., n}] 的排列，但其中一些元素被替换为 #cf_span[0]。两个排列 #cf_span[p] 和 #cf_span[q] 之间的 _距离_ 定义为将 #cf_span[p] 变为 #cf_span[q] 所需的最少移动次数。一次移动由交换 #cf_span[p] 中恰好 #cf_span[2] 个元素组成。
ZS the Coder 希望确定将零替换为集合 #cf_span[{1, 2, ..., n}] 中正整数的方法数，使得 #cf_span[p] 和 #cf_span[q] 都是 #cf_span[{1, 2, ..., n}] 的排列，且它们之间的距离恰好为 #cf_span[k]。
ZS the Coder 希望求出所有 #cf_span[0 ≤ k ≤ n - 1] 的答案。你能帮他吗？
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 250]) —— 排列中元素的个数。
第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n]) —— 排列 #cf_span[p]。保证至少存在一种方式将零替换为正整数，使得 #cf_span[p] 成为 #cf_span[{1, 2, ..., n}] 的一个排列。
第三行包含 #cf_span[n] 个整数 #cf_span[q1, q2, ..., qn] (#cf_span[0 ≤ qi ≤ n]) —— 排列 #cf_span[q]。保证至少存在一种方式将零替换为正整数，使得 #cf_span[q] 成为 #cf_span[{1, 2, ..., n}] 的一个排列。
请输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示 #cf_span[k = i - 1] 时的答案。由于答案可能很大，而 ZS the Coder 喜欢奇怪的素数，请对 #cf_span[998244353 = 223·7·17 + 1]（这是一个素数）取模输出。
在第一个样例中，只有一种方式替换零，使得将 #cf_span[p] 变为 #cf_span[q] 需要 #cf_span[0] 次交换，即 #cf_span[p = (1, 2, 3), q = (1, 2, 3)]。
有两种方式替换零，使得将 #cf_span[p] 变为 #cf_span[q] 需要 #cf_span[1] 次交换。其中一种方式是 #cf_span[p = (1, 2, 3), q = (3, 2, 1)]，此时交换 #cf_span[p] 中的 #cf_span[1] 和 #cf_span[3] 即可得到 #cf_span[q]。另一种方式是 #cf_span[p = (1, 3, 2), q = (1, 2, 3)]，此时交换 #cf_span[2] 和 #cf_span[3] 即可。
最后，有一种方式替换零，使得将 #cf_span[p] 变为 #cf_span[q] 需要 #cf_span[2] 次交换，即 #cf_span[p = (1, 3, 2), q = (3, 2, 1)]。此时，我们可以按如下方式将 #cf_span[p] 变为 #cf_span[q]：。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 250]) —— 排列中元素的个数。第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[0 ≤ pi ≤ n]) —— 排列 #cf_span[p]。保证至少存在一种方式将零替换为正整数，使得 #cf_span[p] 成为 #cf_span[{1, 2, ..., n}] 的一个排列。第三行包含 #cf_span[n] 个整数 #cf_span[q1, q2, ..., qn] (#cf_span[0 ≤ qi ≤ n]) —— 排列 #cf_span[q]。保证至少存在一种方式将零替换为正整数，使得 #cf_span[q] 成为 #cf_span[{1, 2, ..., n}] 的一个排列。
## Output
请输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示 #cf_span[k = i - 1] 时的答案。由于答案可能很大，而 ZS the Coder 喜欢奇怪的素数，请对 #cf_span[998244353 = 223·7·17 + 1]（这是一个素数）取模输出。
[samples]
## Note
在第一个样例中，只有一种方式替换零，使得将 #cf_span[p] 变为 #cf_span[q] 需要 #cf_span[0] 次交换，即 #cf_span[p = (1, 2, 3), q = (1, 2, 3)]。
有两种方式替换零，使得将 #cf_span[p] 变为 #cf_span[q] 需要 #cf_span[1] 次交换。其中一种方式是 #cf_span[p = (1, 2, 3), q = (3, 2, 1)]，此时交换 #cf_span[p] 中的 #cf_span[1] 和 #cf_span[3] 即可得到 #cf_span[q]。另一种方式是 #cf_span[p = (1, 3, 2), q = (1, 2, 3)]，此时交换 #cf_span[2] 和 #cf_span[3] 即可。
最后，有一种方式替换零，使得将 #cf_span[p] 变为 #cf_span[q] 需要 #cf_span[2] 次交换，即 #cf_span[p = (1, 3, 2), q = (3, 2, 1)]。此时，我们可以按如下方式将 #cf_span[p] 变为 #cf_span[q]：。
Let $ n $ be a positive integer, and let $ p, q \in (\{0\} \cup [n])^n $ be two sequences of length $ n $, where $ [n] = \{1, 2, \dots, n\} $, such that:
- Each sequence contains some entries equal to 0 (missing values), and the rest are in $ [n] $.
- The non-zero entries in $ p $ are distinct; similarly for $ q $.
- Let $ A \subseteq [n] $ be the set of values missing from $ p $ (i.e., not appearing among non-zero entries of $ p $).
- Let $ B \subseteq [n] $ be the set of values missing from $ q $.
- Let $ Z_p = \{ i \in [n] : p_i = 0 \} $, $ Z_q = \{ i \in [n] : q_i = 0 \} $ be the sets of indices where $ p $ and $ q $ are zero, respectively.
- Let $ C = A \cap B $, $ A' = A \setminus B $, $ B' = B \setminus A $.
Define the set of valid completions $ \mathcal{P} $ as the set of all pairs $ (\hat{p}, \hat{q}) $ such that:
- $ \hat{p} $ is a permutation of $ [n] $, extending $ p $ by assigning values from $ A $ to positions in $ Z_p $,
- $ \hat{q} $ is a permutation of $ [n] $, extending $ q $ by assigning values from $ B $ to positions in $ Z_q $.
For a pair $ (\hat{p}, \hat{q}) $, define the **distance** $ d(\hat{p}, \hat{q}) $ as the minimum number of transpositions (swaps of two elements) required to transform $ \hat{p} $ into $ \hat{q} $. This equals $ n - c $, where $ c $ is the number of cycles in the permutation $ \sigma = \hat{p}^{-1} \circ \hat{q} $.
For each $ k \in \{0, 1, \dots, n-1\} $, define:
$$
f(k) = \left| \left\{ (\hat{p}, \hat{q}) \in \mathcal{P} \mid d(\hat{p}, \hat{q}) = k \right\} \right| \mod 998244353
$$
Compute $ f(0), f(1), \dots, f(n-1) $.
API Response (JSON)
{
"problem": {
"name": "E. Complete the Permutations",
"description": {
"content": "ZS the Coder is given two permutations _p_ and _q_ of {1, 2, ..., _n_}, but some of their elements are replaced with 0. The _distance_ between two permutations _p_ and _q_ is defined as the minimum nu",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF715E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "ZS the Coder is given two permutations _p_ and _q_ of {1, 2, ..., _n_}, but some of their elements are replaced with 0. The _distance_ between two permutations _p_ and _q_ is defined as the minimum nu...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "ZS the Coder 被给定两个排列 #cf_span[p] 和 #cf_span[q]，它们都是 #cf_span[{1, 2, ..., n}] 的排列，但其中一些元素被替换为 #cf_span[0]。两个排列 #cf_span[p] 和 #cf_span[q] 之间的 _距离_ 定义为将 #cf_span[p] 变为 #cf_span[q] 所需的最少移动次数。一次移动由交换 #cf_s...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ be a positive integer, and let $ p, q \\in (\\{0\\} \\cup [n])^n $ be two sequences of length $ n $, where $ [n] = \\{1, 2, \\dots, n\\} $, such that:\n\n- Each sequence contains some entries equal t...",
"is_translate": false,
"language": "Formal"
}
]
}