2022牛客五一集训派对day1-G题解（多边形内区域和-欧拉公式）

2022牛客五一集训派对day1-G题解

• 目录
• • 题目描述
  • 输入输出
  • 样例
  • 题解
  • • 题目思路
    • 快速幂应用
    • 题目代码
• 结语

目录 题目描述

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.

输入输出

• 输入描述: The only line contains one odd number n(3 ≤ n ≤ 1000000000), which is the number of vertices.
• 输出描述: Print a single line with one number, which is the answer modulo 1000000007.

样例

示例1
输入
3
输出
1

示例2
输入
5
输出
11

备注:
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.

题解 题目思路

易知该正多边形顶点位于同一圆上，则满足欧拉公式。

已知欧拉公式：V-E+F=2

• E(边数)=n(N边形外围的N条边)+C(n,2)(每两个顶点连线确定一条边)+2*C(n,4)(多边形内的交点必然有两条线经过)
• V(顶点)= n(N边形的N个顶点) + C(n,4)(在圆上的每四个点确定一个交点)
• 由此F(平面内所有区域个数)=E-V+2=C(n,2)+C(n,4)+2
• F1(多边形内部区域个数)=F-n(N边形N条边和圆所围面积个数)-1(圆外)=C(n,2)+C(n,4)-n+1
  

快速幂应用

ll ppow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

题目代码

#include 
using namespace std;
const int maxn = 1e7 + 50;
typedef long long int ll;
const ll mod=1e9+7;
ll n;
ll ppow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
ll C(ll x,ll y){
    ll ans=1;
    for(int i=x;i>=x-y+1;i--){
        ans=ans*i%mod;
    }
    for(int i=1;i<=y;i++){
        ans=ans*ppow(i,mod-2)%mod;
    }
    return ans;
}
int main(){
    cin>>n;
    cout<<(C(n,2)+C(n,4)-n+1+mod)%mod<<endl;
    return 0;
}

结语

---

“遇事不决，可问春风。春风不语，即随本心。”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。

---