Cayley

BZOJ 4766 文艺计算姬

Posted on

完全二分图的生成树计数问题。

这里是作为找规律的题目出现的……
对于这张图的一边 n 个节点,另一边 m 个节点。 其结果为

$$n^{m-1} \times m^{n-1}$$

因为数据非常大,为 1e18 ,long long 也会爆炸
用到了快速乘,快速幂

题意:
计算完全二分图的生成树数量

思路:
公式已给。证明无。
……

AC Code

#include <cstdio>

using namespace std;
typedef unsigned long long ull;

ull fastMul(ull a, ull b, ull mod)
{
    ull ret = 0;
    for (; a; a >>= 1, b = (b + b) % mod)
        if (a & 1)
            ret = (ret + b) % mod;
    return ret;
}

ull fastPow(ull x, ull a, ull mod)
{
    ull ret = 1;
    for (; a; a >>= 1, x = fastMul(x, x, mod))
        if (a & 1)
            ret = fastMul(ret, x, mod);
    return ret;
}
int main()
{
    ull n, m, p;
    scanf("%lld %lld %lld", &n, &m, &p);
    printf("%lld\n", fastMul(fastPow(n, m - 1, p), fastPow(m, n - 1, p), p));
    return 0;
}
Cayley

BZOJ 1430 小猴打架

Posted on

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

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