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

这里是作为找规律的题目出现的……
对于这张图的一边 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;
}
Categories: Cayley

发表评论

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

Related Posts

Cayley

BZOJ 1430 小猴打架

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