牛客网暑期ACM多校训练营(第八场) G Counting regions

  • 2018-08-11
  • 42
  • 0

Description:

Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to draw a regular polygon with n vertices. He connected every pair of the vertices by a straight line as well. He counted the number of regions inside the polygon after he completed his picture. He was wondering how to calculate the number of regions without the picture. Can you calculate the number of regions modulo 1000000007? It is guaranteed that n is odd.

Input:

The only line contains one odd number n(3 ≤ n ≤ 1000000000), which is the number of vertices.

Output:

Print a single line with one number, which is the answer modulo 1000000007.

Sample Input:

3

Sample Output:

1

Sample Input:

5

Sample Output:

11

Hint:

The following picture shows the picture which is drawn by Niuniu when n=5. Note that no three diagonals share a point when n is odd.

img

题目链接

先观察顶点数和结果的关系:

vertices ans
3 1
4 4
5 11
6 24
7 50

之后丢入OEIS中(手动滑稽……并不会正解)

即可得到此数列的详细介绍,根据公式求出结果

a(n) = \frac{24 – 42n + 23n^2 – 6n^3 + n^4}{24}

因为此题有取模运算,所以需要求出24对1e9+7的逆元进行计算。

AC代码:

评论

还没有任何评论,你来说两句吧