[bzoj省选十连测推广赛1B]文艺计算姬

2019-11-06 06:06:23

字体：大中小

来源：转载

供稿：网友

题目大意

求一个完全二分图的生成树个数

行列式算算

构造基尔霍夫矩阵的余子式，发现是这样的：这里写图片描述先用上面n-1行每一行都去加第n行。然后第n行变成n-1个m-1然后一个1再来m-1个1-n 用下面m-1行每一行都去加第n行。然后第n行变成只有后m个位置是1。用第n行去加前n-1行，就把那堆-1消掉了。然后变成下三角矩阵，行列式就是主对角线的乘积。 nm−1∗mn−1 $n^{m-1}*m^{n-1}$

#include<cstdio>#include<algorithm>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;int i,j,k,l,t;ll n,m,mo,ans;ll qsc(ll x,ll y){ if (!y) return 0; ll t=qsc(x,y/2); t=(t+t)%mo; if (y%2) t=(t+x)%mo; return t;}ll qsm(ll x,ll y){ if (!y) return 1; ll t=qsm(x,y/2); t=qsc(t,t); if (y%2) t=qsc(t,x); return t;}int main(){ scanf("%lld%lld%lld",&n,&m,&mo); ans=qsc(qsm(n,m-1),qsm(m,n-1)); PRintf("%lld/n",ans);}

上一篇：【Codeforces 781 A Andryusha and Colored Balloons】+ DFS

下一篇：求质数（素数）算法及其改进