UVa 10219

UVa 10219

題目

http://domen111.github.io/UVa-Easy-Viewer/?10219

求 $C_{m}^{n}$ 的數值是幾位數

想法

我們要求的是 $log_{10}{(C_{m}^{n})}+1=log_{10}{(\frac{n!}{(n-m)!m!})}+1$ 取整數後的值

已知

  • $log{\frac{a}{b}}$ = $loga-logb$
  • $logab = loga + logb$


$$log_{10}{(\frac{n!}{((n-m)!m!)})} \
= log_{10}{n!}-log_{10}{((n-m)!m!)} \
= \sum_{i=1}^{n}(log_{10}{i}) - log_{10}{(n-m)!}-log_{10}{m!} \
= \sum_{i=1}^{n}log_{10}{i}-\sum_{i=1}^{n-m}log_{10}{i}-\sum_{i=1}^{m}log_{10}{i} \
= \sum_{i=n-m+1}^{n}log_{10}{i}-\sum_{i=1}^{m}log_{10}{i}
$$

又因為 $n-(n-m+1) = m-1$ ,也就是說可以保證兩個 Sigma 跑的次數是相同的

所以在實作上只需要一個迴圈即可

另外,計算 $C_{m}^{n}$ 時,當我們的 $n\ /\ 2>m$ 時,可以轉換成 $C_{n-m}^{n}$ ,讓數值變得更小一點

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cmath>
using namespace std;
int n,m;
int main(){
while(cin>>n>>m){
double ans=0;
if(n/2 <= m){
// 需要轉換
m=n-m;
}
// 從1開始跑到m
int i=1;
while(i<=m)
ans += (log10(n--) - log10(i++));
cout<<(int)ans+1<<'\n';
}
return 0;
}

時間複雜度分析

每次計算時間約為 $O(1)$,而需要計算 $m$ 次,每筆測資時間複雜度為 $O(m)$