考虑到对于 \(n\) 个点的连通块，那就有 \(n\) 条边，就是个基环树。
如果这里面有 \(1\) 个 \(-1\)，那么就是 \(n - 1\) 条边，就是一棵树。
如果有 \(2\) 个 \(-1\)，\(n - 2\) 条边一定不连通，不可能出现。
令 \(-1\) 的个数为 \(c\)。
那么先对于已知的边连上，如果一个连通块是基环树就直接加上 \(n^c\) 即可。
对于剩下的树，设有 \(m\) 颗，子树大小为 \(siz_i\)。
考虑到一棵树如果接到基环树上那么连通块个数不会变。
所以只有当树内部连成基环树时能多一个连通块。
同时这个基环树也可以当作先拼成环，然后其他的树连上来。
于是就只需要统计这 \(k\) 颗树连成环的方案数了。
考虑如果 \(i\) 在环里，那么只需要连到 \(siz_i\) 这些点就行了。
于是假如环的边的端点选取的方案数就是 \(\prod siz_i\)。
还有环的排列方案数，假设有 \(c\) 个点，考虑固定一个点，对于它来说有 \(c - 1\) 种方案数，对于第二个点就有 \(c - 2\) 种，以此类推，方案数为 \((c - 1)!\)。
同时对于剩下 \(m - c\) 颗树可以随便选，\(n^{m - c}\)。
所以令选出来的树为 \(p_{1\sim c}\)，方案数即为 \(\prod\limits_{i = 1}^c siz_{p_i}\times (c - 1)!\times n^{m - c}\)。
对于前面的 \(\prod\limits_{i = 1}^c siz_{p_i}\) 可以通过背包得到。
即设 \(f_i\) 为选了 \(i\) 颗树的方案数，就有转移 \(f'_i = f_i + f_{i - 1}\times siz\)。
时间复杂度 \(O(n^2)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 998244353;
const int maxn = 2e3 + 10;
int fa[maxn], siz[maxn], vis[maxn];
inline int getfa(int x) {return x == fa[x] ? x : (fa[x] = getfa(fa[x]));}
int to[maxn];
i64 f[maxn], fac[maxn], pw[maxn];
int main() {
int n; scanf("%d", &n);
std::iota(fa, fa + n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &to[i]), to[i] != -1 && (fa[getfa(i)] = getfa(to[i]));
int c = 0;
for (int i = 1; i <= n; i++) siz[getfa(i)]++, to[i] == -1 && (vis[getfa(i)] = 1, c++);
pw[0] = fac[0] = 1;
for (int i = 1; i <= c; i++) pw[i] = pw[i - 1] * n % mod;
for (int i = 1; i <= c; i++) fac[i] = fac[i - 1] * i % mod;
f[0] = 1;
i64 ans = 0;
for (int i = 1; i <= n; i++) if (i == getfa(i)) {
if (! vis[i]) {(ans += pw[c]) %= mod; continue;}
for (int j = c; j; j--) (f[j] += f[j - 1] * siz[i]) %= mod;
}
for (int i = 1; i <= c; i++) (ans += f[i] * fac[i - 1] % mod * pw[c - i]) %= mod;
printf("%lld\n", ans);
return 0;
}