LOJ#6044. 「雅礼集训 2017 Day8」共（Prufer序列）

题面

传送门

题解

答案就是\(S(n-k,k)\times {n-1\choose k-1}\)

其中\(S(n,m)\)表示左边\(n\)个点，右边\(m\)个点的完全二分图的生成树个数，它的值为\(n^{m-1}m^{n-1}\)，证明可以看这里

居然没想出来……

//minamoto #include<bits/stdc++.h> #define R register #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; int n,m,k,P,res,inv[500005]; inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;} int ksm(R int x,R int y){R int res=1;for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;return res; } int C(int n,int m){inv[0]=inv[1]=1;fp(i,2,n-m)inv[i]=mul(P-P/i,inv[P%i]);int res=1;fp(i,1,n-m)res=mul(res,inv[i]);fp(i,m+1,n)res=mul(res,i);return res; } int main(){ // freopen("testdata.in","r",stdin);scanf("%d%d%d",&n,&k,&P),m=n-k;res=mul(ksm(k,m-1),ksm(m,k-1));res=mul(res,C(n-1,k-1));printf("%d\n",res);return 0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10717309.html

总结

以上是生活随笔为你收集整理的LOJ#6044. 「雅礼集训 2017 Day8」共（Prufer序列）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。