Problem Statement
There are N points in the plane. These points are the vertices of a strictly convex N-sided polygon. The points are labeled from 1 to N in clockwise order.
The vertices of the polygon are in a general position. In particular, it is guaranteed that no three diagonals of the polygon intersect at the same point.
We are now going to draw the boundary of the polygon and some diagonals, as follows:
- Each vertex is either good or bad. The probability that vertex i is good is (i / N).
- For each vertex i, we draw a line between vertices i and (i % N) + 1: these are the sides of the polygon.
- For each pair of non-adjacent vertices i and j, we draw the diagonal between i and j if and only if both i and j are good.
Once the drawing is done, the inside of the polygon will be divided into some number of regions. Let X be the expected number of those regions. It can be shown that X is always a rational number. Moreover, if we express X as a reduced fraction P / Q, the denominator Q is not a multiple of 1000000007.
Compute and return the value (P * Q^(-1)) modulo 1000000007.
Definition
- Class:
- PolygonalRegions
- Method:
- expectedRegions
- Parameters:
- int
- Returns:
- int
- Method signature:
- int expectedRegions(int N)
- (be sure your method is public)
Notes
- A polygon is strictly convex if the angle at each vertex is strictly smaller than 180 degrees.
- The choice whether a vertex is good or bad is only made once and applies to all diagonals from that vertex. It is not made separately for each diagonal.
- Q^(-1) denotes the multiplicative inverse to Q modulo 1000000007. That is, (Q * (Q^(-1)) modulo 1000000007 = 1.
- It can be shown that the answer does not depend on the coordinates of the vertices of the polygon.
Constraints
- N will be between 3 and 100, inclusive.
Examples
3
Returns: 1
There is only one region as no diagonals can be drawn.
4
Returns: 31250002
The expect number of regions is equal to 57/32. P(1 region) = P(no diagonal existing) = 13/32 P(2 regions) = P(exactly 1 of the diagonals existing) = 16/32 P(3 regions) = 0 P(4 regions) = P(both diagonals existing) = (1/4) * (2/4) * (3/4) * (4/4) = 3/32 Expected value = (13*1 + 16*2 + 3*4)/32 = 57/32.
10
Returns: 346100029
20
Returns: 123262880
100
Returns: 166669813
99
Returns: 830404246
98
Returns: 191246784
97
Returns: 838588170
96
Returns: 892016455
95
Returns: 762529515
94
Returns: 128639701
93
Returns: 876819373
92
Returns: 109837964
91
Returns: 138274182
90
Returns: 753489948
52
Returns: 964042001
52
Returns: 964042001
82
Returns: 163689586
51
Returns: 385853570
93
Returns: 876819373
23
Returns: 705762154
33
Returns: 878642319
39
Returns: 762088567
4
Returns: 31250002
46
Returns: 930504247
79
Returns: 421739154
12
Returns: 91001210
45
Returns: 879098408
9
Returns: 734339301
10
Returns: 346100029
50
Returns: 265764074
54
Returns: 487194643
14
Returns: 246537996
91
Returns: 138274182
55
Returns: 304536961
57
Returns: 783295301