P2181 刷题记录

傳統藝能:題面地址
剛開始感覺這題滿簡單的,應該能寫O(1)的算法,然而定睛一看題目感覺臉都腫了……
先說一下我寫這道題的思路吧,凸多邊形對角線交點數量參考了沈文德老師的論文[1],發覺是一個排列組合問題,以我初中數學的知識顯然無法求解。求一個n個頂點的凸多邊形的對角線交點,採用公式(C(n-4, n))求解。
百度得(C(r, n)=frac{n!}{r!(n-r)!}),遞歸一下套下公式,應該沒問題的……
代碼如下(C):

#include <stdio.h>

int factorial(int n) {
    int result;
    if(n == 0 || n == 1) return 1;
    else {
        result = factorial(n);
        return result;
    }
}

int C(int n){
    int r = n - 4;
    int up = factorial(n);
    int down = factorial(r) * factorial(n-r);
    int result = up / down;
    return result;
}

// C(r, n) = n!/[r!(n-r)!]
// C(n-4, n)

int main() {
    int n;
    scanf("%d", &n);
    int result = C(n);
    printf("%d", result);

    return 0;
}

但是,你以爲這就完了嗎?
不,並沒有。很顯然這個算法的時間複雜度是難以想象的大,在(n=3)時就已經爆炸了,不用說(nleq10^5)的情況了。於是厚顏無恥的看了題解,果然,O(1)的算法是存在的,佢佢還是佢佢。
大佬通過排列組合的技巧推得了關於n的公式,(frac{n (n-1)}{{2 (n-2)}div{3(n-3)}div4})。然後就不需要階乘了,直接輸出就好了。果然我就是菜啊:-)。
優化後的代碼如下:

#include <stdio.h>

unsigned long long n, ans;

int main() {
    scanf("%lld", &n);
    ans = n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4;
    printf("%lld
", ans);

    return 0;
}

最後放上兩種方法的測試結果(慘):
第一種(自己)
第二種(大佬)

參考文獻:
[1] 一个计算凸多边形对角线交点的方法[J]沈文德.蘇州教育學院學報.1996
[2] ww3113306 P2181題解 包括公式推導過程

原文地址:https://www.cnblogs.com/kozumi/p/12760390.html