Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 4766: 文艺计算姬

题目链接

传送门

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

想说的话

奋战三星期,造台计算机,大家都来看,谁也买不起

题解

结论题
考虑Prufer编码证明
根据Prufer编码的定义我们知道,在一棵树的Prufer编码构建完成之后,剩下的一定是两个相连的点。
那么对于本题来说,考虑一棵合法生成树的prufer序列的生成过程,最后剩下的两个点既然有边,那一定属于二分图中不同的两个集合,即除这两个点外,每个点都被删除了一次。而删除时会将当时与被删除点有边的点加入prufer序列中,那根据二分图的性质(连边只在不同集合点之间),A集合中的点被加进prufer序列中m-1次,B集合中的点被加进n-1次,则生成树个数为[n^(m-1)]*[m^(n-1)],得证。

坑人

所有的乘法用快速乘

代码

Add a Comment

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

隐藏