SRM 460 Div I…一种数学方法

。。。这个题目的官方题解还是很霸气的。。。复杂的动态规划。。。

但其实也是有比较简单的数学方法。。。

题目:http://www.topcoder.com/stat?c=problem_statement&pm=10773&rd=14146

题目简述:给一个图,里面每对点之间最多有两条简单路径(可以没有)。。

让你加入一些边。。使得每对点之间都有1或两条简单路径。。。

求加入边的方法数(顺序无视)。。。

首先。。可以发现结果的图最多只有一个环。。。

考虑结果无环的情况。。也就是当前就没有环。。

然后考虑目前的联通分量..设大小为v1,v2,v3。。。。vM。。。

那么把联通分量看成一个点。。考虑这M个点之间所有的生成树。。

考虑一个特定的生成树。。

设vi的度数为di。。那么这个情况对结果的贡献就是所有vi^di的积。。

根据prufer-code。。这样的可能性的个数是C(M-2,d1-1,d2-1,d3-1…dM-1)。。

C(N,a1.aM)表示把N个数染成M种颜色,第i种颜色有ai个的情况数。。。

把所有结果都+起来。。

那么答案就是。。

Mult(v1..vM)*Sum(v1..vM)^n-2
Mult表示括号内所有数的和。。。

。。。然后考虑有环的情况。。

有两种。。一种是环在一个联通分量内部。。这很好解决。。

还有一种是环在联通分量之间。。

那么枚举环上的元素是哪些。。把这些元素看成一个大的节点就可以了。。。

3 thoughts on “SRM 460 Div I…一种数学方法

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>