题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4766
题意：求一个两边点数分别为 n,m 的完全二分图生成树个数，答案对 p 取模
先放结论
$$ans=n^{m-1}*m^{n-1}$$
可以打表找一找... 蒟蒻尝试用 prufer 编码证一下
首先考虑 prufer 编码的构建过程，最终生成一个 n-2 的序列后一定剩下两个有边相连的点，那么这两个点一定分别属于 A 集和 B 集，那么其它每个点都被删除一次，删除时会向 prufer 序列中加入一个和删除点有边相连的点，那么这个点一定属于另一个集合，所以 A 集合点被加入 m-1 次，B 集合加入 n-1 次.... 换句话说，我们得到的编码是一个由 m-1 个 A 集合点和 n-1 个 B 集合点构成的序列...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n,m,p; ll quick_mul(ll a,ll b,ll m) { ll ans=0; while(b) { if(b&1) { ans=(ans+a)%m; b--; } b>>=1; a=(a+a)%m; } return ans; } ll quick_mod(ll a,ll b,ll m) { ll ans=1; while(b) { if(b&1) { ans=quick_mul(ans,a,m); b--; } b>>=1; a=quick_mul(a,a,m); } return ans; } ll ans,ans1,ans2; int main() { n=read(),m=read(),p=read(); ans1=quick_mod(n,m-1,p); ans2=quick_mod(m,n-1,p); ans=quick_mul(ans1,ans2,p); printf("%lld",ans); } |
Comments | NOTHING