【BZOJ4766】文艺计算姬（prufer序列）

点此看题面

大致题意： 让你求一个两边各有\(n\)和\(m\)个点的完全二分图有多少个生成树。

\(prufer\)序列

这是一道比较经典的利用\(prufer\)序列结论求解答案的计数题。

大致思路

考虑一张二分图求解\(prufer\)序列，由于\(prufer\)序列求解时最后剩下的两个点必定有边相连，因此这两个点必定在二分图两侧。

由于\(prufer\)序列中记录的是每个点相邻的点，也就是说，删去一个左边的点，则就会有一个右边的点被加入\(prufer\)序列。

因此，序列中共会有\(n-1\)个右边的点和\(m-1\)个左边的点。

所以答案就是\(m^{n-1}\cdot n^{m-1}\)。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename Ts>

#define Reg register

#define RI Reg int

#define RL Reg LL

#define Con const

#define CI Con int&

#define CL Con LL&

#define I inline

#define W while

#define LL long long

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

#define Qinv(x) Qpow(x,X-2)

using namespace std;

LL n,m,X;

I LL Qmul(RL x,RL y) {RL t=0;W(y) y&1&&Inc(t,x),(x<<=1)>=X&&(x-=X),y>>=1;return t;}//快速乘

I LL Qpow(RL x,RL y) {RL t=1;W(y) y&1&&(t=Qmul(t,x)),x=Qmul(x,x),y>>=1;return t;}//快速幂

I LL XSum(CL x,CL y) {return x+y>=X?x+y-X:x+y;}//取模优化求和

int main()

{

    scanf("%lld%lld%lld",&n,&m,&X),printf("%lld",Qmul(Qpow(n,m-1),Qpow(m,n-1)));//计算并输出答案

    return 0;

}

巴特西

【BZOJ4766】文艺计算姬（prufer序列）

\(prufer\)序列

大致思路

代码

最新文章

热门文章