BZOJ1430 小猴打架 < Prufer序列+组合数学 >

Problem

小猴打架

$\mathrm{Time\;Limit:\;5\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

一开始森林里面有$N$只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过$N-1$次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当$N=3$时，就有$\lbrace1-2,1-3\rbrace$ $\lbrace1-2,2-3\rbrace$ $\lbrace1-3,1-2\rbrace$ $\lbrace1-3,2-3\rbrace$ $\lbrace2-3,1-2\rbrace$ $\lbrace2-3,1-3\rbrace$六种不同的打架过程。

Input

一个整数$N$，$N\le10^6$

Output

一行，方案数$\mod{9999991}$。

Sample Input

4

Sample Output

96

标签：Prufer序列 组合数学

Solution

由$\mathrm{Prufer}序列$可知，一棵有$n$个点的树与一个长为$n-2$的序列一一对应。那么确定出这样的序列的方案数即可确定最后形成的树的形态。易知这样的序列共有$n^{n-2}$个。再考虑构建树的顺序，即为$n-1$个元素的全排列数，总数为$(n-1)!$。故答案为 $n^{n-2}-(n-1)!\mod{9999991}$。

Code

#include <bits/stdc++.h>
#define MOD 9999991
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;    lnt ans = 1;
int main() {
    read(n);
    for (int i = 1; i <= n-2; i++) (ans *= 1LL*n) %= MOD; 
    for (int i = 1; i <= n-1; i++) (ans *= 1LL*i) %= MOD;
    return printf("%lld\n", ans), 0;
}