#P5406. [2018年湖南省队集训]Gift

    ID: 4418 传统题 1000ms 256MiB 尝试: 116 已通过: 54 难度: 9 上传者: 标签>CF2600省选/NOI-置换循环分解二分图建模第一类 Stirling 数生成函数求系数计数 DP

[2018年湖南省队集训]Gift

[2018 年湖南省队集训] Gift

题目描述

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

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

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

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

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

由于答案可能很大,请将所有答案对 998244353998244353 取模。

输入格式

第一行输入一个整数 nn,表示序列长度。

第二行输入 nn 个整数 A1,A2,…,AnA_1,A_2,\ldots,A_n。

第三行输入 nn 个整数 B1,B2,…,BnB_1,B_2,\ldots,B_n。

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

数据保证,在序列 AA 和序列 BB 中,除 00 以外的元素分别互不相同。

输出格式

输出一行 nn 个整数。

第 ii 个整数表示:补全后两个排列的相似度恰好为 i−1i-1 的方案数,对 998244353998244353 取模后的结果。

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

样例 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

数据范围

子任务 分值 nn 特殊性质
1 10 n≤10n\le 10 无
2 20 n≤250n\le 250
3 n≤2000n\le 2000 特殊性质 1
4 特殊性质 2
5 30 无

特殊性质:

  1. 对任意 i∈[1,n]i\in[1,n],均有 Ai>0A_i>0 且 Bi>0B_i>0;
  2. 对任意 i∈[1,n]i\in[1,n],均有 Ai=Bi=0A_i=B_i=0。

对于全部数据,n≤2000n\le 2000。

时间与空间限制

  • 时间限制:1s1\text{s}
  • 空间限制:256MB256\text{MB}