前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BZOJ4766: 文艺计算姬

BZOJ4766: 文艺计算姬

作者头像
attack
发布2018-04-11 10:50:28
6780
发布2018-04-11 10:50:28
举报
文章被收录于专栏:数据结构与算法

Description

"奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺

术细胞。普通计算机能计算一个带标号完全图的生成树个数,而文艺计算姬能计算一个带标号完全二分图的生成树

个数。更具体地,给定一个一边点数为n,另一边点数为m,共有n*m条边的带标号完全二分图K_{n,m},计算姬能快

速算出其生成树个数。小W不知道计算姬算的对不对,你能帮助他吗?

Input

仅一行三个整数n,m,p,表示给出的完全二分图K_{n,m}

1 <= n,m,p <= 10^18

Output

仅一行一个整数,表示完全二分图K_{n,m}的生成树个数,答案需要模p。

Sample Input

2 3 7

Sample Output

5

HINT

Source

算法1

结合MatrixTree定理打表或者归纳证明

算法2

根据prufe

r因为prufer序列对应着唯一的一棵树,问题转为计算有多少合法的prufer序列。  “一种生成Prufer序列的方法是迭代删点,直到原图仅剩两个点。”根据prufer序列的性质,最后剩下的两个点一定有一条边,在二分图中有连边的两点一定处于不同集合。在删除时会“移去所有叶子节点(度为1的顶点)中标号最小的顶点和相连的边,并把与它相邻的点的编号加入Prufer序列中”,每删除一个点都需要将与它连边的点加到prufer序列中,而二分图中的边两端的点一定属于不同集合,那么A集合有n-1个点被删除,也就是说B集合中的数需要被加入n-1次,共有$m^n−1$种可能;B集合同理,有m-1个点被删除,也就是说A集合中的数需要被加入m-1次,共有n^m−1种可能。  两种情况相乘得到答案为n^{m−1}∗m^{n−1}

代码语言:javascript
复制
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN=1e6+10,INF=1e4+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int fastmul(int a,int p,int mod)
{
    int base=0;
    while(p)
    {
        if(p&1) base=(base+a)%mod;
        a=(a+a)%mod;
        p>>=1;
    }
    return base;
}
int fastpow(int a,int p,int mod)
{
    int base=1;
    while(p)
    {
        if(p&1) base=fastmul(base,a,mod)%mod;
        a=fastmul(a,a,mod)%mod;
        p>>=1;
    }
    return base;
}
main()
{
    int N=read(),M=read(),P=read();
    printf("%lld",fastmul(fastpow(N,M-1,P),fastpow(M,N-1,P),P)%P);
     return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-02-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档