Codeforces Div2 418E

Description

求满足如下条件的 $N$ 个点的简单无向图的个数对 $ 1e9 + 7 $ 取模的结果:

  • 每个点的度数均为 $2$ 或 $3$
  • 从一号点到任何一个点的最短路唯一并且随着点标号上升而不降.

(两个图不同当且仅当边的集合不同).
$N <= 50$

Solution

我们可以记:

  • $f_{i, j}$ 表示考虑完前 $i$ 个点, 最后一层恰好有 $j$ 个点, 且最后一层之前的点度数已经满足条件时的方案数.
  • $g_{i, j, k}$ 表示当前层有 $i$ 个点, 上一层剩下来 $j$ 个度为 $2$ 的点, $k$ 个度为 $3$ 的点时连边的方案数.

那么容易得到$f_{i, j} = \sum_{k} f_{i-j, k} \times g_{j, c0, c1}$, 其中$c0\,,c1$表示最后一层 $k$ 个点中度为 $2$ 的点和度为 $3$ 的点的个数.

对于 $g$, 不难得到:

$$
g_{i, j, k} =
\begin{cases}
1 & i = 0, j = 0, k = 0 \\
\sum_{l=2}^{k-1} \frac{l!}{2} {k-1 \choose l} g_{i, j, k-l-1} & i = 0, j = 0, k > 0 \\
(j-1) \cdot g_{i, j-2, k} + k \cdot g_{i, j, k-1} & i = 0, j > 0 \\
j \cdot g_{i-1, j-1, k} + k \cdot g_{i-1, j+1, k-1} & i > 0
\end{cases}
$$

Hint

注意在第二个递推式中 $l$ 从 $2$ 开始枚举, 因为不能有重边, 所以不存在大小为 $2$ 的环.