UVa 10213 How Many Pieces of Land? (组合数学 & 图论)
题目
题目大意
有一块椭圆形的地。在边界上选\(n\)(\(0 ≤ n < 2^{31}\))个点并两两连接得到\(\frac{n(n - 1)}{2}\)条线段
题解
关于这个问题还有维基百科: Dividing a circle into areas
再推荐一个讲解视频: 【官方中配】分圆问题，诡异的数列规律：解答篇
在这道题里, 椭圆和圆没什么区别, 不要在这上面纠结。
首先我们考虑两件事情: 1. 圆里有多少条直线; 2. 圆里的直线有多少个交点。
对于第一个问题, 题目上已经告诉了是\(\frac{n(n - 1)}{2}\), 但我还是想说一下怎么算的:
给圆上的点编号, 可以将每一条直线用一个二元组\((a, b)\)表示。首先考虑\(a\)， 有\(n\)种选择, 这时\(b\)还剩下\(n - 1\)种选择, 根据乘法原理, 可以得到\(n(n - 1)\)。又因为计算时会有重复(如\((2, 6)\)和\((6, 2)\)), 所以要再除以\(2\), 得到一共有\(\frac{n(n - 1)}{2}\)条直线, 也就是\({n \choose 2}\)条。
第二个问题, 为了让区域最多, 不能有两条以上直线交于一点的情况。也就是说每一个交点对应两条直线, 也就可以用这两条直线在圆上的\(4\)个点表示。根据乘法原理, 可以得到\(n(n - 1)(n - 2)(n - 3)\)。同样的, \(4\)个数有\(4!\)种排列, 将其除以\(4!\), 得到有\(\frac{n(n - 1)(n - 2)(n - 3)}{1 × 2 × 3 × 4}\)个点, 也就是\({n \choose 4}\)个。
接下来我们用图论来解决它。
图中的结点总数为圆内的加上圆上的一共\({n \choose 4} + n\)个; 易总结出已有的直线中每有一个交点就会增加两条线段, 不能理解可以画图看看, 则圆中边的总数为已有的\(n \choose 2\)加上两倍交点数\(2{n \choose 4}\), 再加上圆上\(n\)个点构成的\(n\)条边, 得到边的总数为\({n \choose 2} + 2{n \choose 4} + n\)。
根据欧拉示性数公式\(V - E + F = 2\)(即点的数量减去边的数量加上图中区域的数量等于\(2\)), 可以得到\(F = {n \choose 2} + 2{n \choose 4} - {n \choose 4} + 2 = {n \choose 2} + {n \choose 4} + 2\), 再减去圆外的大区域得到答案为:
\[{n \choose 2} + {n \choose 4} + 1\]
也就是
\[\frac{n!}{(n-4)! 4!}+\frac{n!}{(n-2)! 2!}+1\]
化简得到
\[\frac{n^4 - 6n^3 + 23n^2 - 18n}{24} + 1\]
因为数据范围过大, 需要高精度,
由于我比较懒不想写高精度\(Python\)自带高精度, 就用\(Python3\)写了这道题。
用\(Python\)写的时候要注意,
运算符/的返回值是浮点类型,
输出时即使是整数也会自动保留一位小数,
换成//整除就可以避免这个问题。
代码
1 | T = int(input()) |