简单容斥题。
思路
题面的条件相当于一个位置上填的点不能是自己的祖先。
发现直接做并不好做。
考虑容斥。
我们想要求出 \(f_i\) 为至少有 \(i\) 个不合法位置的方案数。
那么答案为：
\[\sum_{i=0}^n f_i(-1)^i \]如何求解。
设 \(f_{i,j}\) 为 \(i\) 子树下有 \(j\) 个不合法位置的方案数。
第一种转移是普通背包合并。
\[f_{i,j}=\sum_{k=0}f_{s,k}\times f_{i,j-k} \]第二种转移则是此时子树的根填到子树下的一个位置，相当于多了一个不合法位置。
\[f_{i,j}=f_{i,j}+f_{i,j-1}\times (siz_i-j) \]最后在令 \(f_{1,i}=f_{1,i}\times (n-i)!\)，表示其它的点可以随便摆放。
时间复杂度：\(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
#define int long long
int n, ans;
int s[2020], p[2020];
int g[2020], v[2020];
int f[2020][2020];
vector<int> to[2020];
inline void dfs(int x) {
s[x] = f[x][0] = 1;
for (auto i : to[x])
if (i != p[x]) {
dfs(i);
fill(g, g + s[x] + s[i] + 1, 0);
for (int j = 0; j <= s[x]; j++)
for (int k = 0; k <= s[i]; k++)
(g[j + k] += f[x][j] * f[i][k]) %= mod;
copy(g, g + s[x] + s[i] + 1, f[x]);
s[x] += s[i];
}
for (int i = s[x]; i >= 1; i--)
(f[x][i] += f[x][i - 1] * (s[x] - i)) %= mod;
}
signed main() {
cin >> n;
for (int i = 2; i <= n; i++) cin >> p[i];
for (int i = 2; i <= n; i++) to[p[i]].push_back(i);
dfs(1);
v[0] = 1;
for (int i = 1; i <= n; i++) v[i] = v[i - 1] * i % mod;
for (int i = 0; i <= n; i++) {
(ans += v[n - i] * f[1][i] * (i & 1 ? -1 : 1)) %= mod;
}
cout << (ans + mod) % mod << "\n";
}