b897. 10219 - Find the ways !

n 個貧民窟，獲准拆除其中的 k 個
求拆除的方法數是幾位數

---

解法一、數學

🔹 史特靈公式

題目求方法數，也就是 $C_{k}^{n}$
其中 $k \leq n < 2^{31}$

$2^{31}!$ 是一個非常大的數
很難全部算出後再計算位數
所以需要在計算過程中算位數

另外，可以使用 史特靈公式 計算
史特靈公式會用到 $\pi$ 跟 $e$
可以拿 <cmath> 中的 M_E、M_PI 來用

史特靈公式-wiki

在計算過程中算位數

$C_{k}^{n} = \frac{n!}{k! \; (n-k)!}$

要計算 $C_{k}^{n}$ 的位數可以透過 $log\frac{n!}{k! \; (n-k)!}$

根據對數公式 $log\frac{a}{b} = loga - logb$
$log\frac{n!}{k! \; (n-k)!} = log\:n! - log\:k! - log\:(n-k)!$

✅ 完整代碼

評分結果(參考) ： AC (1ms, 332KB)

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

double log_stirling(int n){
    if(n <= 1) return 0.0;
    return n * log10(n / M_E) + 0.5 * log10(2 * M_PI * n);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    while (cin >> n >> k){
        if (n == k){
            cout << "1\n";
            continue;
        }
        
        int ans = ceil(log_stirling(n) - log_stirling(k) - log_stirling(n-k));
        
        cout << ans << "\n";
    }
    return 0;
}