尤拉公式----关于凸多面体之间顶点数/面数/边数之间的关系

清疚 2023-08-17 16:26 50阅读 0赞

##### 尤拉公式----关于凸多面体之间顶点数/面数/边数之间的关系 #####

若G为一连通之平面图,则**V + F = E + 2**  
其中V代表G中点的个数, F代表G中面的个数, 而E是G的边数.

**应用：在一个圆上给你n****个点，求n****个点可以把圆分为几个区域**

分析：根据欧拉定理可知：边-点+2=区域个数

点：v=n+C(n,4)，四个点有一个交点

边：e=n（圆弧上的）+C(n,2) +2\*C(n,4)，两个点连成一条线，内部的一个交点分两条线为四条线

求圆内部有多少区域，所以算出来的区域个数再减去圆外部的一个区域

所以为C(n,4)+C(n,2)+1

例题：Fence Building  [https://www.jisuanke.com/contest/3104/248391][https_www.jisuanke.com_contest_3104_248391]

题意：在一个圆上给你n个点，求n个点可以把圆分为几个区域

分析：根据欧拉定理可知：边-点+2=区域个数

点：v=n+C(n,4)，四个点有一个交点

边：e=n（圆弧上的）+C(n,2) +2\*C(n,4)，两个点连成一条线，内部的一个交点分两条线为四条线

求圆内部有多少区域，所以算出来的区域个数再减去圆外部的一个区域

所以为C(n,4)+C(n,2)+1

1 #include<iostream>
     2 #include<cmath>
     3 #include<cstdio>
     4 #include<vector>
     5 using namespace std;
     6 long long n;
     7 #define mod 1000000007
     8 #define ll long long
     9 ll mod_pow(ll x, ll n, ll p){
    10     ll res = 1;
    11     while(n){
    12         if(n & 1) res =res * x % p;
    13         x = x * x % p;
    14         n >>= 1;
    15     }
    16     return res;
    17 }
    18 
    19 ll comb(ll n, ll m, ll p){ //求解组合数
    20     if(m > n) return 0;
    21     ll ret = 1;
    22     m = min(n - m, m);
    23     for(int i = 1; i <= m; i ++){
    24         ll a = (n + i - m) % p;
    25         ll b = i % p;
    26         ret = ret * (a * mod_pow(b, p - 2, p) % p) % p;
    27     }
    28     return ret;
    29 }
    30 
    31 ll Lucas(ll n, ll m, ll p){  //卢卡斯定理
    32     if(m == 0) return 1;
    33     return comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
    34 }
    35 
    36 int main(){
    37     int t;
    38     scanf("%d", &t);
    39     for(int i=1;i<=t;i++)
    40     {
    41         scanf("%lld",&n);
    42         long long ans=(Lucas(n,2,mod)+Lucas(n,4,mod)+1)%mod;
    43         printf("Case #%d: %lld\n",i,ans);
    44     }
    45     return 0;
    46 }

转载于:https://www.cnblogs.com/Aiahtwo/p/11320642.html

[https_www.jisuanke.com_contest_3104_248391]: https://www.jisuanke.com/contest/3104/248391