20 三月省选 Day 5 B C

B口罩

太经典的题了,以前这场之后都见过两次了。

考虑钦定 $k$ 条边,然后把这 $k$ 条边删掉,再加入回去,求有多少种树。最后再二项式反演回去即可。

一个结论:有一个 $n$ 个点的森林,其中有 $k$ 个连通块,设每个连通块大小是 $d_i$ ,连边可以形成的树的个数是

考虑 $\text{prufer}$ 序,构造一个长度为 $k-2$ 的值为 $1 \sim n$ 的 $\text{prufer}$ 序。然后还原方法是把连通块看成点,把 $1 \dots k$ 写下来,每次找到最小的没有一个点在 $\text{prufer}$ 出现的连通块拿出来,和首项连边。连边的时候会找到当前连通块的一个点去连。序列长度为 $2$ 则直接分别选一个点连。而每个 $1 \dots k$ 的连通块都正好需要选一次点,所以乘上每个连通块的大小。

然后可以发现,$\prod d_i$ 本质上就是把树分成若干个连通块,每个连通块选正好一个点的方案数。所以我们可以 $dp[u][k][0/1]$ 表示当前在 $u$ 选了 $k$ 个连通块出来了,$u$ 所在连通块是否选点。树形 $dp$ 即可。

复杂度根据某经典证明是 $O(n^2)$ 的。

C 了吗

关于这个题的定义:

可以发现 $S$ 是一个类似求子树大小的时候的 $dp$ 的东西。这种东西往往可以差分:

这样一来,$S$ 就只在求 $V’$ 的时候有用,要求的就是有多少种方案使得整个树的 $V’$ 的和为 $s$ 。

每个点的 $V’$ 有两种情况,要么这个点的 $V’$ 是 $[0,k]$ 中任选的一个数,要么是整个子树除了这个点的 $V’$ 的和。那么考虑一个点 $u$ ,如果它是第二种情况,那么它对根的贡献是什么。会发现,每经历一个第一种祖先,这个点的贡献就会翻倍一次。最后,这个点的贡献一定是 $2^kt_u$ 。

考虑每个点本身,写成一个 OGF 的形式,它的贡献是 $1+x^{2^t}+x^{2\times 2^t} + \cdots + x^{k \times 2^t}$ 这个东西。我们不妨设 $F(x) = 1+x+x^2+ \cdots + x^k$ ,考虑每个 $2^k$ 按 $k$ 分类后,就是 $(F(x^{2^k}))^w$ 这个东西,$w$ 是多少个点贡献是 $2^k$ 。考虑算 $F(x)^w$ 再给它的指数乘上 $2^k$ 。直接拿 $\text{exp}$ 做是可以的,但是常数很大,$10^6$ 不一定能过。

考虑我们要算的其实是

前面那个可以二项式定理展开,然后直接写出来,后面那个就相当于做 $w$ 次 $\{1,0,\dots\}$ 的前缀和,这个东西的式子是很容易写出来的

现在我们相当于有很多多项式 $g_0,\dots g_k$ ,需要算出

考虑倒着计算这个东西,每次先算出 $g_k(x)$ 然后乘上 $g_{k+1}(x^2)$ ,每次乘法都只暴力 $\frac{S}{2^{k}}$ 项,所以复杂度其实是 $(S+\frac S 2 + \frac S 4 + \cdots)\log S = O(S\log S)$ 的。

注意,每次别把长度开成 $3s$ ,这样会导致 NTT 带两倍的常数。最好每次就开 $2s$ ,然后乘了前两个丢掉 $> s$ 的项再乘,这样常数会小一些。

复杂度 $O(S\log S)$ 。

文章作者: yijan
文章链接: https://yijan.co/2020/12/28/20-san-yue-sheng-xuan-day-5-b-c/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog