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 |
|
時間複雜度分析
每次計算時間約為 $O(1)$,而需要計算 $m$ 次,每筆測資時間複雜度為 $O(m)$