2023-10-14

题目

题目描述

[ABC180F] Unbranched

难度&重要性(1~10):7.5

题目来源

CQYC

题目算法

dp,组合数学

解题思路

对于处理方案数问题，我们很容易想到用 dp 解决。

记 \(f_{i,j}\) 表示有 \(i\) 个点，\(j\) 条边时的方案数为多少。转移就是每一次枚举新增 \(k\) 个点为一个连通块，边数就是 \(k,k-1\)，即环和链的情况。

我们还需要考虑去重，因为我们每一次加入去之前相同大小的联通块，就会出现重复计算的情况。如一种方案是先加入 \(\{a\}\) 再加入 \(\{b\}\)，但还存在一种方案是将两者顺序调换过来。对于这种情况我们的处理其实也很简单，我们只需要每次钦定必须将未加入的数中的编号最小的数加入就可以解决了。

对于加入的连通块本身我们也需要去重。

对于链，可以能会存在对称相等的情况，我们需要将点数大于 \(1\) 的除以 \(2\)。
对于环，可以能会存在旋转相等的情况，我们需要将点数大于 \(2\) 的除以连通块大小。

这样我们就可以得到具体的 dp 转移式子了：

\[f_{i,j}\displaystyle\gets_{k=1}^{\min(i,L)} \begin{cases}\dbinom{n-i+k-1}{k-1}k!\times f_{i-k,j-k+1} & j\ge k-1,k=1\\ \\ \dfrac{\dbinom{n-i+k-1}{k-1}k!\times f_{i-k,j-k+1}}{2} & j\ge k-1,k>1\\ \\ \dbinom{n-i+k-1}{k-1}(k-1)!\times f_{i-k,j-k} & j\ge k,k=2\\ \\ \dfrac{\dbinom{n-i+k-1}{k-1}(k-1)!\times f_{i-k,j-k}}{2} & j\ge k,k>2\end{cases} \]

最后，这里我们 \(f_{i,j}\) 的方案数其实是记的连通块大小最大的至多为 \(L\) 的，而我们需要保证最大连通块大小为 \(L\)，就需要在 dp 一个最大连通块至多为 \(L-1\) 的方案数，两者相减即为答案。