就非得写点东西吗

题意

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

题解

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

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

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

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

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

答案是 ,时间复杂度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}

本文采用CC-BY-SA-3.0协议,转载请注明出处
作者: wsy_jim