组合数的大小比较

· · 个人记录

\binom{n}{m}=\dfrac{n!}{m!(n-m)!}

对 \binom{n}{m} 取对数。

\log_2\binom{n}{m}=\log_2\dfrac{n!}{m!(n-m)!}=\log_2 n!-\log_2 m!-\log_2(n-m)!

又有：

\log_2 n!=(\log_2(n-1)!)\cdot n=\log_2(n-1)!+\log_2 n

只需维护这样一个对数的前缀和即可。