大概 $OIer$ 上化学课都会想到这个吧?
- 今天化学课教烷烃的同分异构体,我:这烷烃不就是颗树嘛?同分异构体数目不就是无标号树的个数嘛? $prufer$ 序列随便搞一下就能算吧???
- 然后发现一个碳旁边最多连四个碳,度数还要 $\leq 4$.
- 然后我就问旁边数竞小哥:你知道这个东西的通项嘛?他:我来找下规律.我:这东西(指数树)的规律大概率找不出来吧…他不信邪,结果找了一节课,未果,寻病终…
- 然后在 $dalao$ 们的博客中学习了一下.记 $f(i,j)$ 表示 $i$ 个点的有根树,根节点的度数为 $j$ 的方案数目.
- 在枚举儿子节点时,为了避免算重,按照子树大小从大到小来枚举.先枚举儿子中最大的子树大小 $size$ ,再枚举有 $k$ 个这样大小的儿子.记 $s=\sum_{i=0}^{j-1} f(size,i)$ ,即每个这样的子树都有 $s$ 种方案可选.那么给 $k$ 个子树安排一下方案,就相当于把 $k$ 个球放入 $s$ 个无差别盒子中,方案数为 ${s+k-1\choose k}$ .
- 那么转移方程就有 $f(i,j)=\sum f(i-k\times size,j-k)\cdot {s+k-1\choose k}$ .
- 如果是数烷基,就是无根树,直接就像上面这样算, $ans=\sum_{k=0}^3 f(n,k).$
- 如果数的是烷烃,就是无根树,所以钦定树的重心作为根节点.那么在转移时就要注意 $2\cdot size<i$ ,保证根为重心.
- 另外,在最后计算答案时,注意到当 $n$ 为偶数时,它有两个重心,那么两边的子树可以交换,多乘上 $p_k={\sum_{k’=0}^{k-1}f(\frac n 2,k’)+1\choose 2}$.
- 最后就有 $ans=\sum_{k=0}^3 f(n,k)+[n\equiv 0\mod2]\cdot p_k$ .