E - Counting Spanning Trees

E 猜结论

题意

给一个特殊的二分图，要求你算出它生成树的个数，其中顶点数 $n \le 10^5$

思路

如果图的定点数小于 $n \le 10^2$ ，可以用矩阵树定理爆算，复杂度 $O(n^3)$

但是，这个图很大，尝试猜结论...

首先，从小图开始猜，比如样例3的基尔霍夫矩阵：

[ 1, 0, 0,-1, 0, 0 ],
[ 0, 2, 0,-1,-1,-1 ],
[ 0, 0, 3,-1,-1,-1 ],
[-1,-1,-1, 3, 0, 0 ],
[ 0,-1,-1, 0, 2, 0 ],
[ 0, 0,-1, 0, 0, 3 ]

其 $n-1$ 阶余子式的值为 $ans = 1\times 2 \times 2 \times 1$ , 因此答案为 $4$

比如样例2的基尔霍夫矩阵：

[ 2, 0,-1,-1 ],
[ 0, 2,-1,-1 ],
[-1,-1, 2, 0 ],
[-1,-1, 0, 2 ]

其 $n-1$ 阶余子式的值为 $ans = 2 \times 2$ , 因此答案为 $4$

不妨猜，对这个特殊的二分图，记其度数序列为 $deg(i)$ ，其答案为：

$ans = \frac{\prod deg(x_i)deg(y_i)}{max(deg(x_i))max(deg(y_i))}$

全部评论

推荐最新楼层

10-31 14:34

门头沟学院游戏后端

cvte体验实习

今天上午答辩，问题有些没回答上来。答辩后，hr面薪资都没问，估计是挂咯

吴offer选手：别去了强度太大了

点赞评论收藏

11-04 22:03

武汉理工大学 Java

美团实习四个月等三个月等到转正坏消息

|| 先说下主播个人情况：211本，暑期实习之前有过一段中大厂的后端实习，暑期拿过腾讯的实习offer，综合考虑业务和语言最终去了美团。实习期间体感还是不错的，5月初去的，去了就一直急着要需求做，担心因为没有产出导致转正失败，在第二个星期就和mt透露我希望能够留用。虽然第一个由于美团新人landing的友好性基本没做什么需求，但是后面也写出了小2w行的代码量（不包含单测）。中期经常主动加班赶需求，经常持续一两个星期加班到10点甚至更后面。mt对我确实不错，也是言传身教，实习期间给我讲了很多关于单测，ddd，set化等的理解，也是受益匪浅，此外在做需求的时候，也能看出把比较有含金量的部分交给我做...

菜菜菜小白菜菜菜：我在字节实习了四个月，有转正的压力所以周末大部分也在公司自学，也是因为一些原因转正拖的很久，这个点还没答辩，过段时间才回去答辩。整个不确定性的焦虑贯穿了我的秋招三个月，我也曾经犹豫过是不是应该放弃转正走秋招更快，最后因为沉没成本一直舍不得放弃，前前后后七个月真的挺累的，尤其是没有来字节实习的同学已经校招拿到意向时更加焦虑。这段时间也跟mentor聊了很多次，他告诉我未来工作上或者生活上，比这些更头疼的事情会更多，关键还是要调整好自己的心态。转正没有通过从过程上来看其实跟你自身没太大的关系，拖了三个月不出结果显然是ld的问题，并且今年美团最近的开奖大家似乎都不是很乐观，所以不去也罢。我在字节实习的时候，6月份有一个赶上春招末期的25届同事刚面进来，也拿到了小sp的薪水。不要对这件事有太大的压力，时代的问题罢了

点赞评论收藏