Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

04/6
09:11
prufer序列 快速幂

[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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

考虑生成树的prufer序列,剩下的两个点一定属于不同的集合,所以A集合的n个点在序列中每个出现了m-1次,B集合的m个点出现了n-1次,所以答案就是 m^{n-1}n^{m-1},注意要快速乘

 

[bzoj 4766] 文艺计算姬