[洛谷P4430]小猴打架

题目大意：有$n$个点，问有多少种连成生成树的方案。

题解：根据$prufer$序列可得，$n$个点的生成树有$n^{n-2}$个，每种生成树有$(n-1)!$种生成方案，所以答案是$n^{n-2}(n-1)!$

卡点：无

C++ Code：

#include <cstdio>

const int mod = 9999991;

int n, sum;

inline int pw(int base, int p) {

	static int res;

	for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;

	return res;

}

int main() {

	scanf("%d", &n);

	sum = pw(n, n - 2);

	for (int i = 2; i < n; ++i) sum = static_cast<long long> (sum) * i % mod;

	printf("%d\n", sum);

	return 0;

}

巴特西

[洛谷P4430]小猴打架

最新文章

热门文章