题意: 就是给你一个压缩图的方式,然后让你计算任意选择k(1....n)个点之后的图上剩余点的期望数(mod 1e9+7). 做法: 很显然的得到两个结论(记当前要保留的点为k,总点数为n). 1.对于一个度数小于等于2的点,他的留下来的概率为(n-1,k-1)/(n,k). 因为只有这个点被选到了,才有可能留下来. 2.对于一个度数大于2的点,他留下来的有两种情况,一种是他被选到了, 还有就是他有3个及以上的儿子所在的子树中有点被选到.那么可以得出其概率为 1 -( \sum_{i<j}(si_i + si_j, k) + (m-2) * \sum_i(si_i,k) ) / (N...
投递牛客等公司