PKUSC 2024 D1T3

· · 个人记录

偷学并整理了一下 cxy 的做法。

首先我们明确一下暴力 O(nm^2) 或 O(nm\log m) 是怎么做的。

考虑最大独立集的一种算法：对于点权 a_u，求出序列 b_u = \max\left(a_u - \sum_v b_v, 0\right)，然后 \sum_u b_u 就是答案。

于是立刻有暴力 DP f(u, k) 表示 b_u=k 的方案数。转移时，我们首先将儿子的第二维卷积，并做一次前缀和得到数列 t_k，然后有（其中 s_u 表示 u 的子树大小）

f(u, k) = \begin{cases}m^{s_u} - \sum_{j=0}^{m-1} t_j, & k=0 \\ t_{m-k}, & 1\le k \le m\end{cases}

接下来考虑用 GF 来表达这个 DP。

我们容易验证以上转移等效于任取 a_u=1,\dots,m 之后变换 b_u = \max\left(a_u - \sum_v b_v, 0\right)。

接下来我们注意到转移的时候儿子处只关心 k=0,\dots,m-1 的值，因此我们考虑 f(u, k) 的一个截断的 GF f_u(x) = \sum_{k=0}^{m-1} f(u, k) x^k。

可以归纳证明，存在多项式 g_u(x), h_u(x) 满足 \deg g_u(x), \deg h_u(x) \le s_u 且

f_u(x) = \frac{g_u(x)}{(1-x)^{s_u}} \bmod x^m = \frac{g_u(x)+x^m h_u(x)}{(1-x)^{s_u}}

转移时，我们首先考虑 p(x) = \prod_v g_v(x) 满足 \deg p(x) < s_u，然后容易算出

\sum_{k=0}^{m-1} t_k = \sum_{k=0}^{m-1} [x^k] \frac{p(x)}{(1-x)^{s_u-1+1}} = [x^{m-1}] \frac{p(x)}{(1-x)^{s_u+1}}

接下来，为了取模 x^m，我们需要算出 q(x) 满足

\frac{p(x)}{(1-x)^{s_u}} \bmod x^m = \frac{p(x)+x^m q(x)}{(1-x)^{s_u}}

提取 [x^{m+k}] 可得

[x^k] \frac{q(x)}{(1-x)^{s_u}} = -[x^{m+k}] \frac{p(x)}{(1-x)^{s_u}}

同时容易证明 \deg q(x) < s_u，因此我们只需要对于 k=0,\dots,s_u-1 算出 [x^{m+k}] \frac{p(x)}{(1-x)^{s_u}} 后，再卷上 (1-x)^{s_u} 即可得到 q(x)。前者提取系数同样可得卷积。

记 \Delta=m^{s_u}-\sum_{k=0}^{m-1} t_k，最后我们需要翻转系数并加 \Delta，可以得到

\begin{aligned} \sum_{k=0}^m f(u, k) x^k &= \frac{x^m \left(p(x^{-1})+x^{-m} q(x^{-1})\right)}{(1-x^{-1})^{s_u}} + \Delta \\ &= \frac{(-1)^{s_u} \left(x^{m+s_u} p(x^{-1}) + x^{s_u} q(x^{-1}) \right) + \Delta \cdot (1-x)^{s_u}}{(1-x)^{s_u}} \end{aligned}

注意这里是 f(u, k) 未截断的 GF。

于是我们取 f_u(x) = (-x)^{s_u} q(x^{-1}) + \Delta \cdot (1-x)^{s_u} 即可。同时在答案中累计

\begin{aligned} &\quad\, \sum_{k=1}^m m^{n-s_u} \cdot k \cdot f(u, k) \\ &= \sum_{k=1}^m m^{n-s_u} \cdot k \cdot [x^k] \frac{f_u(x)}{(1-x)^{s_u}} \\ &= m^{n-s_u} [x^{m-1}] \frac1{1-x}\left(\frac{f_u(x)}{(1-x)^{s_u}}\right)' \\ &= m^{n-s_u} [x^{m-1}] \left(\frac{f_u'(x)}{(1-x)^{s_u+1}}-\frac{s_u f_u(x)}{(1-x)^{s_u+2}}\right) \end{aligned}

时间复杂度 O(n^2 \log n)。