「WC2019」数树

「WC2019」数树

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

task0

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

task1

$$Ans=\sum_{E_1} c^{n-|E_1\cap E_2|}=c^n\sum_{E_1}c^{-|E_1\cap E_2|}$$

一个显然的想法是统计$|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$数量，则

$$\begin{aligned} Ans&=c^n\sum_{i=0}^{n-1}f(i)c^{-i} \\ Ans&=c^n\sum_{i=0}^{n-1} g(i) (\frac1c-1)^i \end{aligned}$$

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

$$n^{n-x-2}\prod_ia_i$$

证明见文末Extend部分。

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

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

$$\begin{aligned} f(u,x)\leftarrow^+f(u,x)f(v,y)y \\\\ f(u,x+y)\leftarrow^+f(u,x)f(v,y)w \end{aligned}$$

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

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

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

$$\begin{aligned} f(u,0)&=f(u,0)f(v,0)w+f(u,0)f(v,1) \\\\ f(u,1)&=f(u,0)f(v,1)w+f(u,1)f(v,0)w+f(u,1)f(v,1) \end{aligned}$$

复杂度$\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}$均摊到每次选连通块，得

$$F_i=\sum_{j=1}^i\binom{i-1}{j-1}F_{i-j}j^{j-2}n^2j^2(\frac1c-1)^{j-1}$$

$\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

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

$$\begin{aligned} Ans=c^n(\frac1c-1)^nn!/n^4\sum_{1\le k\le n,\sum a_=n}\frac{1}{k!}\prod_i\frac{n^2}{(\frac1c-1 )(a_i!)}a_i^{a_i}\\\\ =(1-c)^nn!/n^4\sum_{k=1}^n\frac{1}{k!}[x^n](\frac{n^2}{(\frac1c-1)}\sum_{a>0}\frac{a^a}{a!}x^a)^k \end{aligned}$$

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

$$Ans=(1-c)^nn!/n^4[x^n]\exp(\frac{n^2}{\frac1c-1}\sum_{a>0}\frac{a^a}{a!}x^a)$$

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