P11802 【MX-X9-T6】『GROI-R3』Graph
题目描述
给定一张 $n$ 个点的有向图 $G=(V,E)$，点的编号为 $1 \sim n$，其每个点都入度、出度均不大于 $1$。
在出度不大于 $1$ 的有向图中，我们记 $f^k(x)$ 表示点 $x$ 在图上沿着出边走 $k$ 步走到的点（如果走到一个不存在出边的点，则停在该点上）。
进一步定义 $G^k=(V,E')$，其中 $E'=\{(x,f^k(x))\mid x\in V\}$。我们称 $G$ 为 $G^k$ 的 $k$ 次方根。
若一个点入度出度均为 $0$ 则称其为孤立点。
又给定一个正整数 $c$，你需要给 $G$ 增加若干条边得到图 $G'$，使得：
1. 每个节点的入度出度均为 $1$。
2. 若两个非孤立点在 $G'$ 上位于同一连通块$^{\dagger}$，则在 $G$ 上也要位于同一连通块。
3. 图 $G'$ 存在 $c$ 次方根。
求加边的方案总数，答案对 $998244353$ 取模。
$^{\dagger}$：本题中定义有向图连通块为：将所有边视作无向边得到的连通块。
输入格式
无
输出格式
无
说明/提示
令 $a_i$ 表示点 $i$ 的出边指向点的编号。
**【样例解释 #1】**
合法的序列 $a_1,\ldots,a_n$ 有：
- $2,5,1,3,4$。
- $2,5,3,4,1$。
- $2,5,4,1,3$。
**【数据范围】**
**本题采用捆绑测试。**
| 子任务编号 | $n\le$ | $c\le$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| 1 | $5$ | $5$ | | $2$ |
| 2 | $1000$ | $2\times10^9$ | A | $3$ |
| 3 | $10$ | $2\times10^9$ | | $15$ |
| 4 | $20$ | $2\times10^9$ | | $10$ |
| 5 | $100$ | $2\times10^9$ | | $25$ |
| 6 | $500$ | $2\times10^9$ | B | $10$ |
| 7 | $500$ | $2\times10^9$ | | $20$ |
| 8 | $1000$ | $2\times10^9$ | | $15$ |
- 特殊性质 A：保证不存在 $a_i=-1$。
- 特殊性质 B：保证所有 $a_i=-1$。
对于 $100\%$ 的数据，保证 $1\le n\le 1000$，$1\le c\le 2\times10^9$，$1\le a_i\le n$ 或 $a_i=-1$，不存在 $i\ne j$ 使得 $a_i=a_j$ 且 $a_i \ne -1$。