b897 - 10219 - Find the ways !

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從 n 個貧民窟中選擇 k 個進行拆除的方法數，並輸出該數字的位數。實際上，題目要求計算組合數 C(n, k)，然後計算該組合數的十進位位數。

解題思路

由於 n 和 k 的範圍可能導致組合數非常大，直接計算組合數可能會導致溢位。因此，程式碼使用對數來計算組合數。利用對數的性質，將組合數的計算轉化為對數的加減運算，避免了溢位問題。具體來說，C(n, k) = n! / (k! * (n-k)!)，對兩邊取對數，得到 log10(C(n, k)) = log10(n!) - log10(k!) - log10((n-k)!)。程式碼計算 log10(n!) 的方法是從 n 到 max(n - k, k) 進行迴圈，累加每個數字的 log10 值。同樣的方法計算 log10(k!) 和 log10((n-k)!)，然後進行相減。最後，將結果加上 1，得到組合數的十進位位數。程式碼首先將 k 限制為 min(n-k, k)，以減少計算量。

複雜度分析

• 時間複雜度: O(min(n, k))
• 空間複雜度: O(1)

程式碼

#include <iostream>
#include <cmath>
using namespace std;
long n,k,mi;
long combination(long n, long k) {
	double result = 0;
	
	for (long i = n; i > max(n - k, k); --i) {
		result += log10(i);
	}

	for (long j = min(n - k, k); j > 1; --j) {
		result -= log10(j);
	}

	return (long) (result + 1);
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n >> k){
		k=min(n-k,k);
		cout << combination(n,k) << "\n";
	}
}