这道题题意需要认真读

考虑一条边的贡献

左边a乘客b车  右边c车d乘客

那么这条边的贡献系数最多是min(a,c)+min(b,d)

枚举每条边考虑左子树的大小为x则右子树为n-x

只考虑min(a,c)这种状态

假设左边有8辆车

方案数是C(m,8)*x^8*(n-x)^(m-8)

min(a,c)=sigma(i=1~正无穷)[i<=a]*[i<=b]

针对每个a,b从大到小做前缀和

枚举i 然后乘上左边多于i辆车右边多于i个人的方案

 

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论