正奇邊形可以被分割成多少個多邊形
題目鏈接：
本題需要求一個正奇邊形可以被劃分成多少個區域。
一、歐拉示性數公式：
V(n) + F(n) – E(n) = 2
V(n) —–> n邊形的頂點數
F(n) —–> n邊形的面數
E(n) —–> n邊形的邊數
定義C(n,m)為組合數在n個元素中取m個元素的方案數
把圖轉化成適用於歐拉示性數公式的圖的形式：把所有交點當作頂點，把所有的邊分割成小段。
二、V(n)求解：
顯然，因為兩條線段為n邊形上的邊並且是正奇邊形，所以不可能存在平行的情況，即一定會相交於一點，而且交點一定是新產生的點（兩條邊增加一個頂點），不可能是先前存在的頂點。交點有以下兩種情況：
A類點和B類點，均為新增加的點。每個新增加的點需要四個點構成的兩條直線相交得到，所以新增加的點的個數為C(n,4)（組合數），所以總的點數為：
V(n) = C(n,4) + n
三、E(n)求解：
考慮a條線交於b個點可以產生多少條小邊？假設a-1條邊互相平行，交於b個頂點，很容易得到新產生的邊有2*b+a條，推廣到一般情況發現都滿足此關係，故而：
E(n) = C(n,2) + 2*C(n,4)
註：C(n,2)為變的個數，兩個頂點確定一條邊。
C(n,4)為交點的個數，不包含n邊形的頂點。
四、到此V(n)和E(n)均求解完畢，由歐拉示性數公式有：
F(n) = E(n) – V(n) + 2
= C(n,2) + 2*C(n,4) – C(n,4) – n + 2
=C(n,2) + C(n,4) – n + 2
因為最後我們只求n邊形內的圖形區域數量，所以處於n邊形外的區域即最終答案為F(n)-1
即：C(n,2) + C(n,4) – n + 1
程式碼：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll qpow(ll a, ll n)//快速冪a^n
{
ll ans = 1;
ll base = a;
while (n)
{
if (n & 1)
{
ans = ans * base % mod;
}
base = (base * base) % mod;
n >>= 1;
}
return ans;
}
ll C(int n, int m)//組合數求解C(n,m)
{
ll ans = 1;
for (int i = n; i >= n - m + 1; i--)
{
ans = (ans * i) % mod;
}
for (int i = 1; i <= m; ++i)
{
ans = (ans * qpow(i, mod - 2)) % mod;//逆元
}
return ans;
}
int main()
{
ll n;
scanf("%lld", &n);
printf("%lld\n", (C(n, 4) + C(n, 2) - n + 1 + mod) % mod);
return 0;
}
參考：
