好题。（不过绝大部分题解全在瞎说）
看到 $n$ 个点 $n$ 条边且每个点只有一条出边很容易的想到基环树。
而最后每个连通块一定是一个基环树，那么统计连通块的数量就相当于统计基环树的数量。
既然有基环树，这种题绝对不能枚举然后求连通块数量，一定是枚举连通块求它在多少种情况中会出现。
首先先扫一遍，把确定的边用并查集建好，同时维护每个树的点数量，变数量，这样就能够方便判断它是不是一个基环树了。
从基环树森林上断掉任意条边，一定会形成若干颗森林和若干颗基环树，这点十分显然，对于断开后仍是基环树的情况，可以直接统计答案了（因为日后无论怎么连始终是一个连通块），此时记输入的 $a$ 数组中有 $x$ 个 $-1$，方案为 $n^x$。（乘法原理）
接着考虑树，树中一定是有一个点向外连的边还没有确定，如果将这个边连到输入时就有的基环树上，此时的答案我们已经在输入时统计完了，所以唯一剩下的情况就是树连到树上形成基环树。
此时仍然不好考虑，不妨枚举一些东西，枚举这个基环树是由 $k$ 颗树构成的，然后发现倘若这 $k$ 颗树的根分别是 $a_1$ $a_2$ $a_3\cdots a_k$，那么由这些树互相连接组成基环树的方案数为 $sz_{a_1}\times sz_{a_2}\times sz_{a_3}\cdots \times sz_{a_k}$，当然这只是第 $i$ 颗基环树连向第 $i\bmod k+1$ 棵树的方案数。
事实上，我们还要对于这 $i$ 颗树进行排列后第 $i$ 颗连向第 $i+1$ 颗，这样才能不重不漏的计数。
排列的数量为 $k!$，但事实上并不是。
因为 $a_1$ $a_2$ $\cdots a_k$ 和 $a_2$ $a_3$ $\cdots a_k$ $a_1$ 是一样的，这种就是环状的情况，所以要除以 $k$。
如果有 $k$ 颗树 $a_1$ $a_2$ $a_3\cdots a_k$，那么连接成的基环树的数量就是 $(k-1)!\times sz_{a_1}\times sz_{a_2}\cdots \times sz_{a_k}$ 了。
于是枚举完 $k$，$(k-1)!$ 是可以提出来的，就剩下这样一个问题：从长度为 $n$ 的序列中选择 $k$ 项，求这些项的乘积和，设 $F_{i,j}$ 为前 $i$ 个数中选择 $j$ 个的乘积和，这是一个 $n^2$ 的劣质 DP。
此时发现枚举 $k$ 已经没有意义了，我们可以在计算完 $F$ 后，设 $cnt$ 为输入完后统计出树的数量，$F_{cnt,i}\times (i - 1)!$ 即为由 $i$ 颗树组成基环树的方案数了。
但答案仅仅如此吗？并不是，因为还有其余的 $-1$ 的 $a$ 没有选取，建基环树消耗了 $i$ 个 $-1$ 节点，剩下的 $-1$ 节点减一减就得到了，设剩下的 $-1$ 节点有 $sum$ 个，还是乘法原理 $n^sum$。
至此，这道题做完了：
#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
using namespace std;
int n, ans, cnt, cnt_1;
int a[2005], fac[2005], sum[2005];
int F[2005][2005];
const int mod = 998244353;
bool f, vis[2005];
int fa[2005], sz[2005], edge[2005];
int q_pow (int x, int y) {
if (y == 0) return 1;
if (y & 1) return x * q_pow (x * x % mod, y >> 1) % mod;
return q_pow (x * x % mod, y >> 1) % mod;
}
int find (int x) {return (fa[x] == x ? x : fa[x] = find (fa[x]) );}
void merge (int x, int y) {
int fx = find (x), fy = find (y);
if (fx == fy) edge[fx] ++;
else {
fa[fy] = fx;
sz[fx] += sz[fy];
edge[fx] += edge[fy] + 1;
}
}
signed main () {
fac[0] = 1;
For (i, 1, 2000) {
fac[i] = fac[i - 1] * i % mod;
fa[i] = i;
sz[i] = 1;
}
cin >> n;
For (i, 1, n) {
cin >> a[i];
if (a[i] == -1) {
++ cnt_1;
continue;
} else merge (i, a[i]);
}
For (i, 1, n) {
if (fa[i] == i) {
if (edge[i] == sz[i]) ans = (ans + q_pow (n, cnt_1) ) % mod;
else sum[++ cnt] = sz[i];
}
}
F[0][0] = 1;
For (i, 1, cnt) For (j, 0, i) {
F[i][j] = F[i - 1][j];
if (j) F[i][j] = (F[i][j] + F[i - 1][j - 1] * sum[i]) % mod;
}
For (i, 1, cnt) {
ans = (ans + F[cnt][i] * q_pow (n, cnt_1 - i) % mod * fac[i - 1]) % mod;
}
cout << ans;
return 0;
}
标签：sz,cnt,int,笔记,times,基环树,ARC140D,mod From： https://www.cnblogs.com/Xy-top/p/17728876.html