20 三月省选 Day 5 B C

B口罩

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

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

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

nk2din^{k-2} \prod d_i

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

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

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

C 了吗

关于这个题的定义:

Su=vsonuVvVv=Su+t,t[0,k]SuS_u = \sum_{v \in son_u} V_v \\ V_v = S_u + t,t \in[0,k] \cup S_u

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

Vu=VuSu=tSu=vsonu(Sv+Vv)=vsubu,vuVvVu=vsubuVvV'_u = V_u - S_u = t\\ S_u = \sum_{v \in son_u} (S_v + V'_v) = \sum_{v \in sub_u , v \neq u} V'_v\\ V_u = \sum_{v \in sub_u} V'_v

这样一来,SS 就只在求 VV' 的时候有用,要求的就是有多少种方案使得整个树的 VV' 的和为 ss

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

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

考虑我们要算的其实是

(1xk+11x)wmodxS=(1xk+1)w(11x)w(\frac{1-x^{k+1}}{1-x})^w \bmod x^S\\ = (1-x^{k+1})^{w} (\frac{1}{1-x})^w

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

ixi(w+i1w1)\sum_{i}x^i \binom{w+i-1}{w-1}

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

g0(x1)g1(x2)g2(x4)g_0(x^1)g_1(x^2)g_2(x^4)\dots

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

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

复杂度 O(SlogS)O(S\log S)

\