[ARC140D] One to One

首先有一个性质，每个点只有一条出边的图，每个联通块只能是基环树。那么有 \(-1\) 的连通块就一定是树。
本题要求的是每种连边方案的联通块数量之和，把贡献拆开来算就可以转化为每个联通块在多少种方案之中出现。
记基环树的个数为 \(x\)， 树的个数为 \(y\)，第 \(i\) 棵树的大小为 \(sz_i\)
首先是已经成为了基环树的联通块，那么显然它的将会在任意一个方案中出现，贡献为 \(n^y\)。
如果树连到基环树上，对答案显然没贡献，所以考虑树之间连边。
对树的联通块贡献按照大小分类 \(g_j\) 表示 \(j\) 棵树的 \(-1\) 点之间连成一个环的方案数。转移就是 \(g_j=g_j + g_{j-1}*sz[i]\)。
最终答案是基环树的贡献加上 \(\Sigma_{i=1}^y g_i \times (i-1)! \times n^{y-j}\)。

Tips：
每个点只有一条出边的图，每个联通块只能是基环树。
把答案的贡献拆开来算可能更好做。

代码：

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 2e3 + 10, mod = 998244353;
vector<int> e[N];
int n, ans, cnt, sz[N], g[N], ne, a[N];
LL fac[N], pw[N]; int vis[N];
inline void dfs(int u) {
	vis[u] = sz[u] = 1;
	for (auto v: e[u]) 
		if (!vis[v]) dfs(v), sz[u] += sz[v];
} 
int v[N];

int main(){
	//FO("");
	read(n);
	pw[0] = fac[0] = 1;
	U(i, 1, n) 
		fac[i] = fac[i - 1] * i % mod, pw[i] = pw[i - 1] * n % mod;

	U(i, 1, n) {
		read(a[i]);
		if (~a[i]) e[i].push_back(a[i]), e[a[i]].push_back(i);
	}

	U(i, 1, n) if (a[i] == -1) dfs(i), v[++cnt] = sz[i];
	U(i, 1, n) if (!vis[i]) dfs(i), update(ans, pw[cnt]);

	g[0] = 1;
	// cerr << ans << "\n";
	U(i, 1, cnt) D(j, i - 1, 0) {
		update(g[j + 1], (LL) g[j] * v[i] % mod);
		// cerr << v[i] << "\n";
	}
	
	U(i, 1, cnt)
		update(ans, (LL) g[i] * fac[i - 1] % mod * pw[cnt - i] % mod);
	writeln(ans);	
	return 0;
}