题目大意:有$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;
}