Ural1387 Vasya's Dad

时间：2024-03-26 13:06:50

Description

Vasya’s dad is good in maths. Lately his favorite objects have been "beautiful" directed graphs. Dad calls a graph "beautiful" if all the following conditions are true:

  • The graph contains exactly \(N\) vertices and \(N−1\) edges.
  • Exactly one vertex has no entering edges.
  • The graph contains no directed cycles.

Dad calls two "beautiful" graphs isomorphic, if the vertices of the first graph can be renumbered in such way that it turns into the second one.

Dad picks an integer \(N\), stocks up blank paper, and draws a "beautiful" graph on each sheet. He verifies that no two drawn graphs are isomorphic.

Given the number \(N\), you are to find the number of sheets that Vasya's dad has to stock up.

Input

Input contains the single integer \(N (1 \le N \le 50)\).

Output

Output the number of "beautiful" graphs with \(N\) vertices.

Sample Input

3

Sample Output

9

题目大意——求\(N\)个点有标号的有根树的数目是多少。

假设\(a_n\)是\(n\)个点的无标号有根树的数目，则有以下的公式：

\[a_n = \sum_{\sum_{i = 1}^{n-1}}[\prod_{k=1}^{n-1}\binom{a_k+c_k-1}{c_k}]
\]

其中\(c_k\)表示根节点的子树中大小为\(i\)的子树有多少个。

为什么是\(\binom{a_k+c_k-1}{c_k}\)，这是个可重组合公式。我们可以这样考虑，我们现在有\(a_k\)中子树可以选，我们可以从中选出\(c_k\)个。那么我们相当于$$\sum_{i = 1}^{a_k}x_i = c_k$$的非负整数解的方案数。也就等价于

\[\sum_{i = 1}^{a_k}x_i = c_k+a_k$$的正整数解的方案数。使用隔板法，不难得出公式
$$\binom{a_k+c_k-1}{a_k-1} = \binom{a_k+c_k-1}{c_k}\]

再用下乘法原理，上述公式就得证了。但是复杂度太高，虽然打表依旧可过。然后我们可以利用生成函数优化公式(母函数)，然而这一块我们看懂。wtz说了用了很高深的解析组合的公式。希望以后学了后我能够看懂，先记在这里。

设$$A(x) = \sum_{n = 0}{\infty}a_nxn$$

基于上述分析可以迅速（tm那里迅速了）得到

\[A(x) = x \times e^{\sum_{r = 1}^{\infty}A(x^r)}
\]

于是就可推导出：

\[a_{n+1} = \frac{1}{n} \times \sum_{i = 1}^n(i \times a_i \times \sum_{j=1}^{\lfloor n/i \rfloor}a_{n+1-i \times j})
\]

wtz还告诉了我假如树无根，那么也有公式：

  • 当\(n\)是奇数时，答案为$$a_n-\sum_{1 \le i \le \frac{n}{2}}a_ia_{n-i}$$
  • 当\(n\)是偶数时，答案为$$a_n-\sum_{1 \le i \le n}a_ia_{n-1}+\frac{1}{2}a_{\frac{n}{2}}(a_{\frac{n}{2}}+1)$$

然后我就用java（因为要高精度）对着公式打，就ac了。

import java.math.*;

import java.util.*;

public class Main

{

	static final int maxn = 55;

	static BigInteger A[] = new BigInteger[maxn]; static int N;

	public static void main(String args[])

	{

		Scanner cin = new Scanner(System.in);

		N = cin.nextInt();

		A[1] = BigInteger.valueOf(1);

		A[2] = BigInteger.valueOf(1);

		A[3] = BigInteger.valueOf(2);

		for (int n = 3;n < N;++n)

		{

			A[n+1] = BigInteger.ZERO;

			for (int i = 1;i <= n;++i)

			{

				BigInteger res; res = BigInteger.ZERO;

				for (int j = 1;j <= n/i;++j) res = res.add(A[n+1-i*j]);

				A[n+1] = A[n+1].add(res.multiply(A[i]).multiply(BigInteger.valueOf(i)));

			}

			A[n+1] = A[n+1].divide(BigInteger.valueOf(n));

		}

		System.out.println(A[N]);

	}

}

相关文章