題目大意：有$n$個(gè)點(diǎn)，問有多少種連成生成樹的方案。

題解：根據(jù)$prufer$序列可得，$n$個(gè)點(diǎn)的生成樹有$n^{n-2}$個(gè)，每種生成樹有$(n-1)!$種生成方案，所以答案是$n^{n-2}(n-1)!$

卡點(diǎn)：無



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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Memory-of-winter/p/10326713.html

總結(jié)

以上是生活随笔為你收集整理的[洛谷P4430]小猴打架的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。