题解：CF2122G Tree Parking
Petit_Souris
·
·
题解
计数基本功题。当然如果你直接贺 poly 板子求欧拉数了那我也没话说。
首先考虑对于一棵固定的树求答案：
可以考虑树形 dp，设 f_u 表示 u 子树的方案数。那么转移时，我们可以任意内部排列所有子树的区间，最后再插入 u 的区间。
$$
f_u=(2sz_u - 1)\prod_v f_v \times \frac{(2sz_u - 2)!}{\prod_v(2sz_v)!}
$$
可以通过考虑每个 $sz_u$ 的计算次数来化简，得到 $f_1 = \frac{(2n - 1)!}{2^{n-1}\prod \limits_{v\neq 1} sz_v}=\frac{(2n)!}{2^n\prod\limits_{v}sz_v}$。
考虑 $\prod\frac{1}{sz_v}$ 的组合意义。我们知道 $\frac{n!}{\prod sz_v}$ 表示树的拓扑序个数，因此我们可以枚举所有可能的拓扑序，计算合法的树的数量，求和后除以 $n!$。而这里所有的 $1$ 开头的拓扑序都是等价的，所以有 $(n-1)!$ 种对称情况，因此最后只需要乘上 $\frac{1}{n}$。
固定拓扑序的情况下计算树的个数是容易的，我们只需要按照拓扑序插入所有的点。设 $dp_{n, k}$ 表示 $n$ 个点的树有 $k$ 个叶子的方案数。那么有转移式 $dp_{n, k} = (n - k) dp_{n - 1, k - 1} + kdp_{n - 1, k}$，两项分别表示把第 $n$ 个点接在叶子下面还是接在根下面。
容易与欧拉数的组合意义建立双射：$dp_{n, k}$ 实际上就是长度为 $n-1$ 的排列，有 $k - 1$ 个相邻上升的排列数量（这里产生 $-1$ 是因为我们把根挖掉了）。
所以问题就变成了求单项欧拉数 $A(n, k)$。可以考虑二项式反演，设 $g_t$ 表示钦定 $t$ 个上升的方案数，那么会形成 $n-t$ 段，每段内部唯一。
这里可以用 EGF 解决，以凑出多重排列的系数：也就是要求 $[x^n](e^x-1)^{n-t}$，因为每段非空。进行展开：
$$
g_t = [x^n](e^x-1)^{n-t}\\
= [x^n]\sum\limits_{i = 1} ^ {n - t} e^{ix}(-1)^{n - t - i}\binom{n - t}{i}\\
=\sum\limits_{i = 1} ^{n - t} i ^n(-1)^{n - t - i}\binom{n-t}{i}
$$
再做二项式反演：答案 $=\sum\limits_{t = k}^{n - 1}\binom{t}{k}(-1)^{t-k}g_t$，带入化简：
$$
\sum\limits_{t = k}^{n - 1}\binom{t}{k}(-1)^{t-k}g_t \\
=\sum\limits_{t = k}^{n - 1}\binom{t}{k}(-1)^{t-k}\sum\limits_{i = 1} ^{n - t} i ^n(-1)^{n - t - i}\binom{n-t}{i}
$$
合并 $-1$ 的幂并交换求和号：
$$
=\sum\limits_{t = k}^{n - 1}\binom{t}{k}\sum\limits_{i = 1} ^{n - t} i ^n(-1)^{n - k - i}\binom{n-t}{i} \\
=\sum\limits_{i = 1} ^{n - k} i ^n(-1)^{n - k - i}\sum\limits_{t = k}^{n - i}\binom{t}{k}\binom{n-t}{i} \\
$$
后面这个组合数求和可以这样考虑：$\binom{t}{k}$ 是 $\frac{1}{(1-x)^{k + 1}}$ 的 $x^{t - k}$ 次项系数，$\binom{n-t}{i}$ 是 $\frac{1}{(1-x)^{i + 1}}$ 的 $x^{n-t-i}$ 次项系数。所以乘起来求和就是 $\frac{1}{(1-x)^{i+k+2}}$ 的 $x^{n-k-i}$ 次项系数，即 $\binom{n + 1}{i + k + 1}$。
因此所求为 $=\sum\limits_{i = 1} ^{n - k} i ^n(-1)^{n - k - i}\binom{n + 1}{i + k + 1}$。
最终答案为：
$$
\frac{(2n!)}{n2^n}\sum\limits_{i=1}^{n-k}i^{n-1}(-1)^{n-k-i}\binom{n}{i + k}
$$
$\mathcal O(n)$ 计算即可。