#P5453. Permutation

    ID: 4459 传统题 1000ms 512MiB 尝试: 24 已通过: 6 难度: 7 上传者: 标签>难度分类提高+/省选-图论强制相邻链压缩构造与建模奇偶性分析多项式与生成函数指数生成函数导数积分转化组合数学递推计数双射计数CF2300

Permutation

Permutation

题目描述

对一个长度为 nn 的排列 pp,构造一张有向图,顶点编号为 1,…,n1,\ldots,n,对每个 ii 连一条从 ii 到 pip_i 的边。每个点的入度和出度都是 11,因此这张图由若干个互不相交的有向环组成。

如果每个环的长度都是偶数,就称这个排列为好排列。现在有些位置的值已经指定,求有多少个好排列满足所有指定值,答案对 998244353998244353 取模。

输入格式

第一行一个正整数 nn。第二行 nn 个整数 b1,…,bnb_1,\ldots,b_n,其中 0≤bi≤n0\le b_i\le n。bi=0b_i=0 表示 pip_i 未指定,否则要求 pi=bip_i=b_i。

输出格式

输出一行一个整数,表示答案对 998244353998244353 取模后的结果。

样例

6
0 0 0 0 0 0
225

数据范围

1≤n≤1000001\le n\le100000。