nCr

二項係数 $_n \mathrm{C} _r$ の高速計算の実装に手こずった。 サトゥー$n$ が莫大で $r$ が比較的小さいときに有効な二項係数の計算です。 あかりさんは $n$ 種類の花を&nb […]

AtCoder の問題を解いていると、 mod p の条件下で高速に二項係数 nCr を求める場面に多く遭遇するのでそのあたりの知識をまとめます。 二項係数 nCr を計算する まずは普通に計算してみましょう。これは二項 […]