Codeforces 1667E Centroid Probabilities

这个连边方式就可以理解为 \(1\) 为根，点 \(u\) 的父亲 \(fa_u\) 满足 \(fa_u < u\)。

重心有不止一种表示法，考虑用“子树 \(siz\ge \lceil\frac{n}{2}\rceil\) 最深的点”来表示重心。

令 \(m = \lceil\frac{n}{2}\rceil\)，\(f_i\) 为节点 \(i\) 的 \(siz\ge m\) 的方案数。
考虑枚举 \(siz = j\) 最后求和。
首先要从 \(i + 1\sim n\) 中选出 \(j\) 个点，\(\binom{n - i}{j - 1}\)。
对于子树内非 \(i\) 的节点的父亲就只能是子树的点，又因为 \(fa_u < u\)，方案数为 \((j - 1)!\)。
子树外的节点的父亲就不能是子树的点，因为同样的限制，方案数 \((n - j - 1)!\)。
对于 \(i\) 自己就可以选择 \(1\sim i - 1\) 的点作为 \(fa_i\)，方案数 \(i - 1\)。
于是有：
\(f_i = \sum\limits_{i = m}^n \binom{n - i}{j - 1}\times (j - 1)!\times (n - j - 1)!\times (i - 1)\)
\(= \sum\limits_{i = m}^n \frac{(n - i)!}{(n - i - j + 1)!}\times (n - j - 1)!\times (i - 1)\)
\(= (n - i)! \times (i - 1)\sum\limits_{i = m}^n \frac{(n - j - 1)!}{(n - i - j + 1)!}\)
\(= (n - i)! \times (i - 1)!\sum\limits_{i = m}^n \frac{(n - j - 1)!}{(n - i - j + 1)!(i - 2)!}\)
\(= (n - i)! \times (i - 1)!\sum\limits_{i = m}^n \binom{n - j - 1}{i - 2}\)
\(= (n - i)! \times (i - 1)!\times \binom{n - m}{i - 1}\)
于是就可以 \(O(1)\) 算出 \(f_i\) 了。

但是还没有保证最深这个限制，考虑若 \(sz_i\ge m\)，其不是重心时重心肯定在其子树内。
因为如果在祖先节点肯定不可能，因为 \(i\) 更深；否则两个点对应的子树无交集，且都满足 \(sz\ge m\)，那么两颗子树的 \(sz\) 和 \(\ge 2m = 2\lceil\frac{n}{2}\rceil\)，因为 \(n\bmod 2 = 1\)，所以 \(2\lceil\frac{n}{2}\rceil > n\)，一定不可能。

于是令 \(g_i\) 为点 \(i\) 为重心的方案数。
那就只需要考虑枚举重心为 \(j \in [i + 1, n]\) 时的方案数减掉即可。
因为点 \(j > i\) 出现在 \(i\) 子树内的概率为 \(\frac{1}{i}\)，所以有 \(g_i = f_i - \frac{\sum\limits_{j = i + 1}^n g_j}{i}\)。

时间复杂度 \(O(n\log n)\)，容易做到 \(O(n)\)。

#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 998244353;
inline i64 qpow(i64 a, i64 b) {
    i64 v = 1;
    while (b) b & 1 && ((v *= a) %= mod), (a *= a) %= mod, b >>= 1;
    return v;
}
inline i64 inv(i64 a) {return qpow(a, mod - 2);}
const int maxn = 2e5 + 10, limn = 2e5;
i64 fac[maxn], finv[maxn];
inline i64 C(int n, int m) {return n < m ? 0 : (fac[n] * finv[m] % mod * finv[n - m] % mod);}
i64 f[maxn];
int main() {
    fac[0] = finv[0] = 1;
    for (int i = 1; i <= limn; i++) fac[i] = fac[i - 1] * i % mod;
    finv[limn] = inv(fac[limn]);
    for (int i = limn; i > 1; i--) finv[i - 1] = finv[i] * i % mod;
    int n; scanf("%d", &n);
    int m = (n + 1) >> 1;
    i64 sum = 0;
    for (int i = n; i; i--) {
        i64 tot = fac[n - i] * fac[i - 1] % mod * C(n - m, i - 1);
        f[i] = (tot - sum * inv(i) % mod + mod) % mod;
        (sum += f[i]) %= mod;
    }
    for (int i = 1; i <= n; i++) printf("%lld ", f[i]);
    return 0;
}