闲话 25.9.8

闲话

怎么所有人开学都比我晚？？？？

一个多月没写鲜花了 听了好多歌

推歌环节：
揉揉头 by 春卷饭 ft. 初音未来 & 看護機＿型号Ｔ;
坠入霜星 by 初音未来 et al.;
泡沫 by 廉 et al.;
八月的雨 remixed by 708/残響P;
‘你自时间消失后成为我自己’ by 及時作夢 ft. 洛天依/乐正绫;
皮肉 by Magens ft. 初音ミク;
海の底でいきている by ごめんなさいが言えなくて ft. 鏡音鈴;
水星に融ける by HotaRu ft. 初音ミク.

小周严选！

网络赛的一道（不是很 gf 的）gf 题

Asia EC Online 2025 (I) K

给定 \(n\)，对所有 \(m, k\)，计数 \(n\) 个点、恰好有 \(m\) 个点有 \(k\) 个孩子的无标号有根有序树。

\(n\le 10^5\)。

从 qoj 提交上看没人和我（与 APJifengc）的式子一样啊！我写写做法。

因为 \(mk \le n\)，我们枚举做的复杂度是对的。首先确定 \(k > 0\)，令 \([x^n y^m]F\) 为此时的答案（\(F[0, 0] = 0\)），那么显然有

\[F = x\left(\dfrac{1}{1-F} - F^k + yF^k\right) \]

也就是

\[\dfrac{F}{(1-F)^{-1} + (y-1) F^k} = x \]

这自然导出了 \(F\) 关于 \(x\) 的复合逆。从而根据拉格朗日反演（怎么我感觉我身边所有人都只记得 \(1.4.1\) 的形式），答案就是

\[\begin{aligned} [x^ny^m] F &= \dfrac{1}{n} [x^{n-1} y^m] \left(\dfrac{1}{1-x} + (y-1) x^k\right)^{n} \\ &= \dfrac{1}{n} [x^{n-1} y^m] \sum_{i = 0}^n \binom{n}{i} y^i x^{ki} \left(\dfrac{1}{1-x} - x^k\right)^{n-i} \\ &= \dfrac{1}{n} \binom{n}{m} [x^{n-1 - km}] \left(\dfrac{1}{1-x} - x^k\right)^{n-m} \\ &= \dfrac{1}{n} \binom{n}{m} \sum_{i = 0}^{n-m} (-1)^{n-m-i}\binom{n-m}{i} [x^{n-1-km}] \dfrac{x^{k(n-m-i)}}{(1-x)^{i}} \\ &= \dfrac{1}{n} \binom{n}{m} \sum_{i = 0}^{n-m} (-1)^{n-m-i}\binom{n-m}{i} [x^{ki-1-(k-1)n}] \dfrac{1}{(1-x)^{i}} \end{aligned} \]

这里需要注意的是，我们不能直接上指标反转后按二项式系数编码 \(i\) 的范围，而应当在提取系数前确定：\(ki - 1 - (k-1)n\ge 0\)，即 \(i \ge \lceil n - \frac{n-1}{k}\rceil = n - \lfloor \frac{n-1}{k} \rfloor\)。接着写得到

\[= \dfrac{1}{n} \binom{n}{m} \sum_{i = n - \lfloor \frac{n-1}{k} \rfloor}^{n-m} (-1)^{n-m-i}\binom{n-m}{i} \binom{(k+1)i-(k-1)n-2}{i-1} \]

这时再回去看 \(i\) 的范围。若我们仅仅将 \(i\) 的范围编码进这式子，会出现负指标组合数的情况，就爆炸了。

注意到目前的式子是可以通过卷积对每个 \(m\) 计算的。首先平移 \(i' = i - n + \lfloor \frac{n-1}{k} \rfloor\) 使得 \(i\) 的范围变为 \(0 \sim \lfloor \frac{n-1}{k} \rfloor - m\)，此时求和单项就会变成一个 \(f_i\) 乘 \(1/(\lfloor \frac{n-1}{k} \rfloor - m - i)!\) 的形式。仔细写一写就能对每个 \(k\) 以 \(O(\mathrm M(n/k))\) 的复杂度计算。

这部分的总时间复杂度即为 \(\sum_{k = 1}^n O(\mathrm M(n/k))= O(n\log^2 n)\)。

当然 \(k = 0\) 的时候我们可以直接算出其为 \(\dfrac{1}{n} \dbinom{n}{m} \dbinom{n-2}{m-1}\)，特判一下 \(n = 1\) 即可。

Submission.