1 solutions

  • 0
    @ 2025-3-28 15:10:05

    题目说:它的任何三条对角线都不会交于一点。

    注意到,任意一个交点,都是两条对角线形成的。

    同时,任意两条对角线,是四个顶点形成的。

    那么n个顶点有多少对角线的交点,就是 C(n,4)=n(n1)(n2)(n3)/4!C(n, 4) = n * (n - 1) * (n - 2) * (n - 3) / 4!

    如果直接在最后除以4! = 24会爆掉,注意到n与n - 1一定有一个是2的倍数,n与n - 1与n - 2一定有一个是3的倍数,同理,4的倍数。拆开进行除法,避免运算的时候爆掉。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    typedef multiset<ll>::iterator itt; 
    const int N = 5e6+11, P = 998244353;
    
    unsigned long long n; 
    
    int main(){
    	cin>>n;
    	n = n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;
    	cout<<n<<endl;
      return 0;
    }
    
    
    

    Information

    ID
    538
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    144
    Accepted
    1
    Uploaded By