二項係数

$ {_n}C_k \: mod. \: p

典型

$ 1 \leq k \leq n \leq 10^7

$ {_n}C_k = \frac{n!}{k!(n-k)!}=n! \times (k!)^{-1} \times ((n-k)!)^{-1}

nが巨大でkが小さいとき

$ k \leq 10^7 \leq n

$ {_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

リファレンス