日期：2025年8月7日
ZeroJudge 題目連結：b897. 10219 - Find the ways !
解題想法
這題就是在計算組合數 $$ C^n_k = \frac{n!}{(n-k)! k!} = \frac{n(n-1)(n-2) \dots (n-k+1)}{k(k-1)(k-2) \dots \times 2 \times 1} $$ 取 $\log_{10}$ $$ \begin{align*} ans &= \log_{10} n + \log_{10} (n-1) + \log_{10} (n-2) + \dots + \log_{10} (n-k+1) \\ & ~~~~- (\log_{10} k + \log_{10} (k-1) + \log_{10} (k-2) + \dots + 0) \end{align*} $$ 最後再無條件進位到整數即為答案。
改用史特靈公式取近似，由其中一個表達式史特靈級數 $$ \ln n! = n \ln n - n + \frac{1}{2} \ln (2 \pi n) + \frac{1}{12n} - \frac{1}{360n^3} + \dots $$ 若忽略高次項並用換底公式換成以10為底的對數 $$ \begin{align*} \frac{\log_{10} n!}{\log_{10} e} &= n \cdot \frac{\log_{10} n}{\log_{10} e} - n + \frac{1}{2} \cdot \frac{\log_{10} (2 \pi n)}{\log_{10} e} \\ \log_{10} n! &= n \log_{10} n - n \log_{10} e + \frac{1}{2} \log_{10} (2 \pi) + \frac{1}{2} \log_{10} n \\ \log_{10} n! &\approx (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \end{align*} $$ 因此 $C^n_k$ 取 $\log_{10}$ $$ \begin{align*} & \\ \log_{10} C^n_k \approx & (n + 0.5) \log_{10} n - 0.4343 n + 0.39909 \\ & - [(n-k + 0.5) \log_{10} (n-k) - 0.4343 (n-k) + 0.39909] \\ & - [(k + 0.5) \log_{10} k - 0.4343 k + 0.39909] \end{align*} $$ 但是上式的第二行中有 $\log_{10}(n-k)$，當 $n=k$ 時會出問題，程式碼之中需要排除這個特例。
Python 程式碼
理論上用 math 函式庫中的 comb 可以很方便地計算組合數，但是這個函式在 Python 3.8 才加入，ZeroJudge 網站的 Python 版本為 3.6.9，不能用。
from math import comb, log10, ceil
import sys
for line in sys.stdin:
n, k = map(int, line.split())
print(ceil(log10(comb(n, k))))
改成不使用 comb，直接取 log10 ，還是會超時。
from math import log10, ceil
import sys
for line in sys.stdin:
n, k = map(int, line.split())
if n == k: print("1")
else:
ans = 0
for i in range(n, n-k, -1): ans += log10(i)
for i in range(k, 1, -1): ans -= log10(i)
print(ceil(ans))
使用時間約為 17 ms，記憶體約為 3.3 MB，通過測試。
from math import log10, ceil
import sys
def fac(x):
return (x+0.5)*log10(x) - 0.4343*x + 0.39909
for line in sys.stdin:
n, k = map(int, line.split())
if n == k: print("1")
else: print(ceil(fac(n) - fac(n-k) - fac(k)))
