[51nod]1677 treecnt【组合数学】

1677 treecnt

【题目描述】

传送门

【题解】

我们单独拎出一条边来看。
如下图。

我们设左边节点个数为X,右边为Y,当然X+Y=n。
所以当前边经过的次数就是,C(n,K)-C(X,K)-C(Y,K),要扣掉K个全在X或Y的情况。
然后DFS一下就可以了。

代码如下

#include<cstdio>
#include<cctype>
#include<algorithm>
#define MAXN 100005
#define LL long long
using namespace std;
const int MOD=1000000007;
int n,K;
bool vis[MAXN];
LL Ans,Fac[MAXN],Inv[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN<<1],son[MAXN<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
LL qsm(LL a,LL b){
    LL Ans=1;
    for(;b;b>>=1,a=(a*a)%MOD)
    if(b&1) Ans=(Ans*a)%MOD;
    return Ans;
}
void Make_Fac(){
    Fac[0]=1;
    for(int i=1;i<=100000;i++) Fac[i]=Fac[i-1]*i%MOD;
    Inv[100000]=qsm(Fac[100000],MOD-2);
    for(int i=99999;i>=0;i--) Inv[i]=Inv[i+1]*(i+1)%MOD;
}
LL C(int x,int y){
    if(x<y) return 0;
    return ((Fac[x]*Inv[y]%MOD)*Inv[x-y])%MOD;
}
int DFS(int x,int fa){
    int Siz=1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]^fa){
        int TMP=DFS(E.son[j],x);Siz+=TMP;
        Ans=((Ans+C(n,K)-C(TMP,K)-C(n-TMP,K))%MOD+MOD)%MOD;
    }
    return Siz;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1677.in","r",stdin);
    freopen("1677.out","w",stdout);
    #endif
    n=read();K=read();Make_Fac();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        E.Add(x,y);E.Add(y,x);
    }
    DFS(1,0);
    printf("%lld\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部