二項係数
$ {_n}C_k \: mod. \: p
典型
$ 1 \leq k \leq n \leq 10^7
前処理:$ O(N)
クエリ:$ O(1)
$ {_n}C_k = \frac{n!}{k!(n-k)!}=n! \times (k!)^{-1} \times ((n-k)!)^{-1}
nが巨大でkが小さいとき
$ k \leq 10^7 \leq n
計算量:$ O(k)
$ {_n}C_k = \frac{n}{1} \times \frac{n-1}{2} \times\dots\times\frac{n-k+1}{k}
$ \sum_{k=0}^n{_n}C_k = 2^n
リファレンス