BZOJ 4766 文艺计算姬

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

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