简单容斥题。
思路
题面的条件相当于一个位置上填的点不能是自己的祖先。
发现直接做并不好做。
考虑容斥。
我们想要求出 \(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 longint 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";
}
