直线分割圆-公式递推
题目:圆上有N个点,每个点和其他所有点之间都有直线相连。并且任意3线不共点。计算这些直线把圆分割所得的区域的数量K。
例如:N = 2,K = 2,N = 3,K = 4。由于结果可能会很大,输出K Mod (10^9 + 7)的结果。
Input
输入:1个数N。(2 <= N <= 10^9)
Output
输出数量 Mod 10^9 + 7
Input 示例
2
Output 示例
2
题目分析:
参考:http://bbs.csdn.net/topics/300104643
直接这样考虑就行了:
线段(An+1,Ai)左边有i-1个点,右边有n-i个点,
显然,任意左右两点间的连线都与(An+1,Ai)相交,总共是(i-1)*(n-i)个交点
所以增加的块数是(i-1)*(n-i)+1
这样,增加一个点后,总共增加:∑[(i-1)*(n-i)+1]块,其中i从1到n求和。
这个求和仅用到平方与自然数数列和公式,结果立等可取:n(n^2-3n+8)/6
于是,递推公式为:
f(n+1)=f(n)+n(n^2-3n+8)/6
利用f(1)=1,累加起来有f(n)=1+∑i(i^2-3i+8)/6,其中i从1到n-1。
这个求和最多用到三次数列的求和,结果依然立等可取:f(n)=(n^4-6n^3+23n^2-18n+24)/24
解法二:
先分析:
增加一个点后其中的一个典型线段所多划分的区域显然是O(n^2),所以总共增加的区域数为O(n^3)
递加项是O(n^3),显然通项那就是O(n^4)的,也就是说f(n)是个四次多项式,即
f(n)=a*n^4 + b*n^3 + c*n^2 + d*n +e
五个参数,需要五个方程
手绘1-5的情况,可以数得:f(1)=1,f(2)=2,f(3)=4,f(4)=8,f(5)=16
联立之后即可解出通项公式
关键代码:
ans = ( n4 - n3 * 6 + n2 * 23 - n * 18 + 24 ) / 24 % P; if( ans < 0 ) ans += P; return (int) ans;
补充:软件开发 , C++ ,