組み合わせ数
区別ある$ n個のものから$ k個選ぶ通り$ \binom nkは、
$ \binom nk = \frac{n!}{(n-k)!k!}
ただし、$ n<0 \lor k<0 \lor n<kのとき$ 0とする。
$ n_{max}以下の階乗の値を$ O(n_{max})で前計算して置けば各$ \tbinom nkについて$ O(1)で求められる。
MODをとる場合は、割り算のためMODの逆元を計算する必要がある。 また、$ nが大きいが$ kが小さいとき、以下のように再帰的求めると$ O(k)
$ \binom nk = \frac{n-k-1}{k} \binom {n}{k-1}
$ \sum_{i=0}^{k} \binom{N}{i} = \binom{N+1}{k}