codeforces 439 C – The Intriguing Obsession (和图有关的计数,组合数学)

题意:

3个岛屿群,每个岛屿群有若干岛屿。现在要在岛屿之间连桥,桥的长度是1,规定2个属于相同岛屿群的岛屿的距离要大于等于3.

思路:

一直在纠结大于等于3的距离的事情。。。其实这句话等价于,同一个岛屿,对于另外两个岛屿群,都最多只能连接1个岛屿。

那么其实,对于每一对岛屿群,是相互独立的。

对于任意一对岛屿群,设两边岛屿的数量分别为a,b

我们可以从两边各取0个,1个,最多取min(a,b)

需要注意的是,选取了端点之后有顺序的区别。

所以对于该对岛屿,答案是SUM{C[a][k] * C[b][k] * k!}   (k属于0..min(a,b) )

对于其他 两对同理。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz