【深基2.习7】对角线

解题思路

任选四个顶点，按环上顺序连接相对顶点，就形成唯一一对相交对角线。反过来每个内部交点对应四个端点，因此答案为组合数 C(n,4)。先约去分母 24 的因子再相乘。

正确性说明

凸多边形中对角线内部相交时四端点互异，交替出现；任选四点可组成唯一一组交叉对角线。没有三条对角线共点保证不同组不计为同一点，因此构成双射。

易错点

n 最大 10^5，最终结果可用 long long，但未约分的四数乘积会溢出，必须先除掉分母因子。

复杂度

时间 O(1)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    if (n < 4) {
        cout << 0 << "\n";
        return 0;
    }
    long long a[4] = {n, n - 1, n - 2, n - 3}, d = 24;
    for (int i = 0; i < 4; i++) {
        long long x = a[i], y = d;
        while (y) {
            long long t = x % y;
            x = y;
            y = t;
        }
        a[i] /= x;
        d /= x;
    }
    long long ans = 1;
    for (int i = 0; i < 4; i++)
        ans *= a[i];
    cout << ans << "\n";
    return 0;
}