menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[二分图+矩阵树定理]LOJ6044(雅礼集训 2017 Day8)【共】题解
apps LOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $n$ 个点的树,$1$ 为根,每个节点的深度定义为到根的点数。求深度为奇数的点恰好为 $K$ 的树的个数。

解题报告

emm……我们把树按照深度奇偶分开,就变成了一个二分图,两边点数为 $K,n-K$ 。

然后就是求这个完全二分图的生成树个数……直接上结论:$K^{n-K-1}(n-K)^{K-1}$ 。

所以答案就是 ${n-1\choose K-1}K^{n-K-1}(n-K)^{K-1}$ 。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=500000;

int n,K,MOD,fac[maxn+5],INV[maxn+5],c[1005][1005];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD;
    for (int i=c[0][0]=1;i<=1000&&i<=n;i++) for (int j=c[i][0]=1;j<=i;j++) AMOD(c[i][j]=c[i-1][j],c[i-1][j-1]);
}
inline int C(int x,int y){
    if (x<y) return 0;if (x<=1000&&y<=1000) return c[x][y];
    return (LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD;
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&K,&MOD);Make(n);
    printf("%lld\n",(LL)C(n-1,K-1)*Pow(K,n-K-1)%MOD*Pow(n-K,K-1)%MOD);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up