题解 P7275 【计树】

2021-01-16 23:32:52


对于一条边,如果它连接的两个端点的编号之差的绝对值不超过$1$,我们称这两个端点“连通”。

通过观察不难发现,最终我们得到的每个连通块都是一条长度不小于$2$的链,并且这条链上的点的编号是连续的一段区间。

接下来我们将构建整棵树看作一个这样的过程:

  1. 将$1\sim n$分为$k$个区间,每段区间的长度不小于$2$。
  2. 每段区间内部只有一种连边的方法,接着我们用$k-1$条边将这$k$个连通块连接起来。注意不能再有类似$(i,i+1)$这样的连边,我们称包含这种连边的情况为不合法情况。

比如当$n=4,k=2$时,有如下几种情况:

image.pngimage.pngimage.pngimage.png

此时我们认为$\{1,2\}$是一个连通块,$\{3,4\}$是一个连通块,根据上面的定义,上面的四种情况中,前三种情况都是合法的,而最后一种情况不合法。

在计数的时候直接去除不合法的状态较为困难,因此可以考虑容斥。

记$f(i)$表示将$1\sim n$分为$i$个连通块(也就是区间),再连接$i-1$条边,可能出现不合法情况的方案数。

考虑如何计算$f$,假设我们已经将这$i$个区间分好了,第$i$个区间的大小为$a_i$。显然我们有$\sum a_i=n$,对于新加入的每条边来说,如果它的两个端点分别落在第$u$个区间以及第$v$个区间中,那么$u$这个端点有$a_u$种选法,$v$这个端点有$a_v$种选法。换言之,最终如果第$i$个连通块的度数为$j$,那么答案就要乘上$a_i^j$。

考虑对这棵树的prufer序计数。在prufer序中,一个点出现的次数为度数$-1$,而我们想要的贡献是$\prod a_i^j$。

因此我们可以将一个确定的$a_i$序列的贡献看作prufer序中所有出现$a_i$的乘积,再乘上每个连通块的度数的乘积。对于一个$a_i$来说,它在prufer序中出现了$j-1$次,再加上最后整体乘的一次,贡献恰好为$a_i^j$

由于prufer序的长度为$i-2$,因此实际上这个$a_i$序列的贡献为

$$ \begin{aligned} \prod_{j=1}^ia_j\times (\sum_{k=1}^ia_k)^{i-2}=\prod a_i\times n^{i-2} \end{aligned} $$

我们可以根据这个式子设计一个朴素的$dp$,将$n^{i-2}$拆为$n^i\times n^{-2}$。注意到$n^{-2}$与$a_i$是没有关系的,因此我们在$dp$的过程中可以只考虑$\prod a_i\times n^i$。

记$dp[i][j]$表示将$1\sim i$分为$j$段区间,一组分法的贡献为$\prod a_i\times n^i$时所有方案的和,它可以通过简单的转移求得。

接下来我们需要计算出每个区间的容斥系数,根据广义容斥原理,一组$a_i$的容斥系数为每个$a_i$的容斥系数的乘积。此时每种$a_i$序列的贡献乘上自己的容斥系数再求和就是答案。

我们希望在最终的方案中,长度小于$2$的区间对答案的贡献次数都为$0$,长度大于等于$2$的区间对答案的贡献次数都为$1$。

不妨设$A(x)$是容斥系数的生成函数,$x^i$项的系数就代表长度为$i$的区间对应的容斥系数。对于在最终的一段长度为$i$的区间来说,在我们计算$f$的过程中它有可能被分为若干段小区间,然后在这些小区间之间连上了若干条不合法的边。每种这样的划分都会导致$i$被统计了一次,因此此时每种区间在答案中的统计次数的生成函数为

$$ A(x)+A(x)^2+A(x)^3+\cdots=\frac{1}{1-A(x)}-1 $$

我们希望长度小于$2$的区间被统计的次数都为$0$,因此

$$ \begin{aligned} \frac{1}{1-A(x)}-1&=x^2+x^3+x^4+\cdots\\ &=\frac{1}{1-x}-1-x \end{aligned} $$

解得

$$ A(x)=\frac{x^2}{x^2-x+1} $$

将$A(x)$展开,它的系数非常优美,为$\{0,1,1,0,-1,-1,0,1,1,0,-1,-1,\cdots\}$。

将$dp$写成生成函数的形式,由于$dp$的本质是将$n$划分为$i$段区间,我们有

$$ \begin{aligned} B(x)&=\sum_{j\geq 2}nx^jA_j\\ dp[n][i]&=B(x)^i[x^n]\\ ans&=\sum_i \frac{dp[n][i]}{n^2}\\ &=\sum_i\frac{B(x)^i[x^n]}{n^2}\\ &=\frac{\frac{1}{1-B(x)}[x^n]}{n^2} \end{aligned} $$

调用一次多项式求逆即可。

代码