HDU 2519 新生晚會：組合數計算與精度陷阱

HDU 2519 新生晚會：組合數計算與精度陷阱

計算C(N,M) = N!/(M!(N-M)!) ，N,M ≤ 30。看似簡單的組合數問題，隱藏著整數運算精度陷阱：直接用__int64分步計算可能因中間除法不盡除導致精度損失WA。

解題關鍵：用double避免精度問題

利用乘除交替順序，每步保持結果為整數：

double sum = 1;
for (i = 1; i <= m; i++) {
    sum *= (n--) * 1.0 / i;  // 關鍵：先乘後除，用double保持精度
}
printf("%.0lf\n", sum);  // 輸出整數部分

為什麼這樣做是正確的

C(N,M) = N×(N-1)×...×(N-M+1) / M!
每步計算：sum = sum * (N-i+1) / i
數學上每步結果必為整數，用double可精確表示30以內的所有整數運算（double 52位尾數可精確表示2^53以內整數）。

完整代碼

#include <stdio.h>
int main() {
    int t, i, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        double sum = 1;
        for (i = 1; i <= m; i++) {
            sum *= (n--) * 1.0 / i;
        }
        printf("%.0lf\n", sum);
    }
    return 0;
}

測試樣例

輸入：

5
3 2
5 3
4 4
3 6
8 0

輸出：

3
10
1
0
1

避坑指南

• ❌ 整數分步除法：ans = ans * n / i 可能不盡除截斷
• ❌ 先算階乘再除：數值溢出
• ✅ double乘除交替：精度安全、代碼簡潔
• ✅ M > N 直接輸出0

此題教會我們：組合數計算時，選擇正確的數值類型與運算順序比優化算法更關鍵。