0%

「WC2019」数树

「WC2019」数树

我好菜啊。为什么你们都是数数大师。

task0

求出$E=E_1\cap E_2$,答案为$c^{n-|E|}$.($c$为颜色种类数)

task1

一个显然的想法是统计$|E_1\cap E_2|=x$的$E_1$数量(即恰好$x$条公共边),但是恰好并不好处理。

考虑$c^{-x}=(\frac{1}c-1+1) ^x=\sum_{i=0}^x\binom{x}i (\frac{1}c-1)^i$

令$f(i)$表示恰好$x$条公共边的$E_1$数量, $g(i)$表示钦定了$i$条公共边的$E_1$数量,则

考虑若已知$x$条边,构成了$n-x$个连通块,大小为$a_1,a_2…a_{n-x}$ 则能连成的树的数量为:

证明见文末Extend部分。

令选择一条公共边的贡献为$w=\frac{1-nc}{nc}$,那么我们就有一个dp:令$f(u,x)$表示考虑以$u$为根的子树,$u$所在连通块大小为$x$的答案(没有乘上$x$,$c^n,n^n$最后乘)

考虑加入一个儿子$v$,转移为:

初值$f(u,1)=1.$复杂度$\mathcal O(n^2)$.

优化是考虑$\prod a_i$的组合意义:每个连通块中选恰好一个点作为关键点的方案数。

令$f(u,0/1)$表示考虑以$u$为根的子树且所在连通块选了/没选 关键点的方案数。

复杂度$\mathcal O(n).$

task2

考虑若已确定$x$条边,构成$m=n-x$个连通块,构成连通块大小分别为$a_1,a_2…a_m$,则能连成的树的数量为$(n^{m-2}\prod a_i)^2=n^{2m-4}\prod a_i^2$

设$F_i$表示考虑$i$个点的答案。枚举最后一块连通块的大小$j$,将$n^{2m}$均摊到每次选连通块,得

$\binom{i-1}{j-1}$是确定了一个点的情况下另外选出$j-1$个点的方案数,$j^{j-2}$是这个连通块构成树的方案数,$n^2,j^2$是均摊进来的,后面$(\frac1c-1)^{j-1}$是$j-1$条公共边的贡献。

把组合数拆掉,分治NTT即可做到$\mathcal O(n\log^ 2n)$.

My code

另一种做法是,枚举每个连通块的点数。

后面是个多项式exp,具体就是

由于我的exp是两个log的所以没必要写了