牛客挑战赛48C

就非得写点东西吗

题意

个点，连 条边，形成 棵树，每种方案贡献为这 棵树大小之积，求所有方案贡献和

题解

根据题意，这 棵树肯定为无根树

首先考虑要生成一棵 结点无根树，根据 序列，可以很轻松地求出方案数，如果算上每个方案的贡献，直接 就好了，答案是

发现这跟构造有根树的方案数一样，所以我们可以做一个题意转换，我们令每种方案里确定每棵树的根节点，那么方案数就跟贡献和一样了

我们假设一个虚点 ，令它连接每棵树的根节点，现在就可以算了

一共有 个点， 序列长度为 ，其中点 的度是知道的，有 ，所以在 序列中， 应该出现 次，先选 ，然后剩下的数都是在 ，再 就是答案

答案是 ，时间复杂度

代码

#define int long long

const int Mod=1e9+7;
int n,m;
int ans=1;

int fpow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=a*a%Mod) if(b&1) res=res*a%Mod;
    return res%Mod;
}

signed main(){

    read(n),read(m);

    for(int i=1;i<=m;i++) (ans*=i)%=Mod;
    ans=fpow(ans,Mod-2);
    (ans*=fpow(n,m))%=Mod;
    for(int i=n-m;i<=n-1;i++) (ans*=i)%=Mod;

    cout<<ans<<endl;

    return 0;
}