#P9663. 排列计数

    ID: 6273 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-对称性分析等价类划分埃氏筛最小质因子预处理排列数计算乘法原理

排列计数

题目描述

这天,小 A 遇到了一道他最讨厌的排列计数题:求有多少个长度为 nn 的排列 pp 满足 $\gcd(i,j)=1\Leftrightarrow\gcd(p_i,p_j)=1 (1\le i<j\le n)$。

tzc_wk 看罢,觉得题目太简单了,于是添加了一些限制 (i,v)(i,v) 表示钦定 pi=vp_i=v。

请你求满足上述所有条件的 nn 阶排列个数,对 998244353998244353 取模。

输入格式

第一行一个整数 nn,表示排列长度。

第二行 nn 个整数 pip_i。若 pi=−1p_i = −1 则表示该位没有限制;否则 pip_i 被钦定等于输入值。

输出格式

一行一个整数,表示答案。

样例

5
-1 -1 -1 -1 1
4

排列 [3,2,5,4,1][3, 2, 5, 4, 1],[3,4,5,2,1][3, 4, 5, 2, 1],[5,2,3,4,1][5, 2, 3, 4, 1],[5,4,3,2,1][5, 4, 3, 2, 1] 满足题意。

见附加文件下的 permutation2.in
见附加文件下的 permutation2.ans

该样例满足 Subtask 2 的限制。

见附加文件下的 permutation3.in
见附加文件下的 permutation3.ans

该样例满足 Subtask 3 的限制。

见附加文件下的 permutation4.in
见附加文件下的 permutation4.ans

该样例满足 Subtask 4 的限制。

数据范围

对于 100%100\% 的数据,1≤n≤5×1051\le n\le 5\times 10^5,−1≤pi≤n-1\le p_i\le n,保证若 x≠yx\not=y 且 px,py≠1p_x,p_y\not=1,则 px≠pyp_x\not=p_y。

Subtask 编号 分值 特殊限制
11 2020 n≤10n\le 10
22 n≤20n\le 20
33 pi=−1p_i=-1
44 pi≠−1p_i\not=-1
55 无特殊限制