Cayley

BZOJ 1430 小猴打架

在搜最小生成树计数的题目的时候不小心发现了一个有趣的东西

51nod 1601

完全图的最小生成树计数问题……题解说需要01字典树,不是很会,先放一放
然后就找到了这个资料 Prüfer编码与Cayley公式

简单说完全图的生成树数量为 \( n^{n-2} \)
这个运用矩阵树也可以计算的

题意:
n只猴子打架,两只猴子打架后就会成为好朋友,就不会打架,朋友关系可传递,问打架的序列方案数。

思路:
n个点的生成树数量为 \( n^{n-2} \) ,顺序为 (n-1)!

AC Code

#include <cstdio>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
const int mod = 9999991;
int n;
long long ans = 1;
int main()
{
    scanf("%d", &n);
    range(i, 1, n - 2) ans = ans * n % mod;
    range(i, 1, n - 1) ans = ans * i % mod;
    printf("%lld", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注