Advertisement
wym1111

Untitled

Nov 18th, 2024
38
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //#define int long long
  5. using ll = long long;
  6. const int N = 5e3 + 10;
  7. const ll mod = 998244353;
  8.  
  9. int n;
  10. ll dp[N], g[N][N], mul[N];
  11. int p[N], sz[N];
  12. vector<int> t[N];
  13.  
  14. ll f[N], invf[N], inv[N];
  15.  
  16. ll qpow (ll x, ll k) {
  17.     ll res = 1;
  18.     while (k) {
  19.         if (k & 1) res = res * x % mod;
  20.         x = x * x % mod;
  21.         k >>= 1;
  22.     }
  23.     return res;
  24. }
  25. ll getinv (ll x) {
  26.     return qpow(x, mod - 2);
  27. }
  28.  
  29. void init () {
  30.     cin >> n;
  31.     for (int i = 2; i <= n; i ++) {
  32.         cin >> p[i];
  33.         t[p[i]].push_back(i);
  34.     }
  35.    
  36.     inv[0] = invf[0] = f[0] = 1;
  37.     for (int i = 1; i <= n; i ++) {
  38.         f[i] = f[i - 1] * i % mod;
  39.         inv[i] = getinv(i);
  40.         invf[i] = invf[i - 1] * inv[i] % mod;
  41.     }
  42. }
  43.  
  44. ll dp_sum[N], dp_inv[N];
  45.  
  46. void dfs0 (int x) {
  47.     sz[x] = 1;
  48.     mul[x] = 1;
  49.     dp_sum[x] = 1;
  50.     for (auto y: t[x]) {
  51.         dfs0(y);
  52.         dp_sum[x] = dp_sum[x] * dp[y] % mod;
  53.         sz[x] += sz[y];
  54.         mul[x] = mul[x] * invf[sz[y]] % mod;
  55.     }
  56.     dp[x] = f[sz[x] - 1] * mul[x] % mod * dp_sum[x] % mod;
  57.     dp_inv[x] = getinv(dp[x]);
  58. }
  59.  
  60. ll pre[N][N];
  61.  
  62. ll getC (int x, int y) {
  63.     return f[x] * invf[y] % mod * invf[x - y] % mod;
  64. }
  65.  
  66. void dfs (int x) {
  67.     if (x > 1) {
  68.         for (int i = 1; i <= n; i ++) {
  69.             g[x][i] = pre[p[x]][i - 1] * getC(n - i, sz[x] - 1) % mod;
  70. //          g[x][i] = g[x][i] * f[sz[p[x]] - 1 - sz[x]] % mod * mul[p[x]] % mod * f[sz[x]] % mod;
  71. //          g[x][i] = g[x][i] * dp_sum[p[x]] % mod * dp_inv[x] % mod;
  72.         }
  73.     }
  74.     for (int i = 1; i <= n; i ++) {
  75.         pre[x][i] = (pre[x][i - 1] + g[x][i]) % mod;
  76.     }
  77.     for (auto y: t[x]) {
  78.         dfs(y);
  79.     }
  80. }
  81.  
  82. void solve () {
  83.     init();
  84.     dfs0(1);
  85.    
  86. //  for (int i = 1; i <= n; i ++) {
  87. //      cout << i << " : " << dp[i] << endl;
  88. //  }
  89.    
  90.     g[1][1] = 1;
  91.     dfs(1);
  92.     for (int i = 1; i <= n; i ++) {
  93.         cout << i << " : ";
  94.         for (int j = 1; j <= n; j ++) {
  95.             cout << g[i][j] << " \n"[j == n];
  96.         }
  97.     }
  98.    
  99.     for (int i = 1; i <= n; i ++) {
  100.         cout << g[i][i] * dp[i] % mod << " \n"[i == n];
  101.     }
  102. }
  103.  
  104. signed main () {
  105.     ios::sync_with_stdio(0);
  106.     cin.tie(0);
  107.    
  108.     int _ = 1;
  109. //  cin >> _;
  110.     while (_ --) {
  111.         solve();
  112.     }
  113.    
  114.     return 0;
  115. }
  116.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement