Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //#define int long long
- using ll = long long;
- const int N = 5e3 + 10;
- const ll mod = 998244353;
- int n;
- ll dp[N], g[N][N], mul[N];
- int p[N], sz[N];
- vector<int> t[N];
- ll f[N], invf[N], inv[N];
- ll qpow (ll x, ll k) {
- ll res = 1;
- while (k) {
- if (k & 1) res = res * x % mod;
- x = x * x % mod;
- k >>= 1;
- }
- return res;
- }
- ll getinv (ll x) {
- return qpow(x, mod - 2);
- }
- void init () {
- cin >> n;
- for (int i = 2; i <= n; i ++) {
- cin >> p[i];
- t[p[i]].push_back(i);
- }
- inv[0] = invf[0] = f[0] = 1;
- for (int i = 1; i <= n; i ++) {
- f[i] = f[i - 1] * i % mod;
- inv[i] = getinv(i);
- invf[i] = invf[i - 1] * inv[i] % mod;
- }
- }
- ll dp_sum[N], dp_inv[N];
- void dfs0 (int x) {
- sz[x] = 1;
- mul[x] = 1;
- dp_sum[x] = 1;
- for (auto y: t[x]) {
- dfs0(y);
- dp_sum[x] = dp_sum[x] * dp[y] % mod;
- sz[x] += sz[y];
- mul[x] = mul[x] * invf[sz[y]] % mod;
- }
- dp[x] = f[sz[x] - 1] * mul[x] % mod * dp_sum[x] % mod;
- dp_inv[x] = getinv(dp[x]);
- }
- ll pre[N][N];
- ll getC (int x, int y) {
- return f[x] * invf[y] % mod * invf[x - y] % mod;
- }
- void dfs (int x) {
- if (x > 1) {
- for (int i = 1; i <= n; i ++) {
- g[x][i] = pre[p[x]][i - 1] * getC(n - i, sz[x] - 1) % mod;
- // g[x][i] = g[x][i] * f[sz[p[x]] - 1 - sz[x]] % mod * mul[p[x]] % mod * f[sz[x]] % mod;
- // g[x][i] = g[x][i] * dp_sum[p[x]] % mod * dp_inv[x] % mod;
- }
- }
- for (int i = 1; i <= n; i ++) {
- pre[x][i] = (pre[x][i - 1] + g[x][i]) % mod;
- }
- for (auto y: t[x]) {
- dfs(y);
- }
- }
- void solve () {
- init();
- dfs0(1);
- // for (int i = 1; i <= n; i ++) {
- // cout << i << " : " << dp[i] << endl;
- // }
- g[1][1] = 1;
- dfs(1);
- for (int i = 1; i <= n; i ++) {
- cout << i << " : ";
- for (int j = 1; j <= n; j ++) {
- cout << g[i][j] << " \n"[j == n];
- }
- }
- for (int i = 1; i <= n; i ++) {
- cout << g[i][i] * dp[i] % mod << " \n"[i == n];
- }
- }
- signed main () {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int _ = 1;
- // cin >> _;
- while (_ --) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement