izumo’s diary

主に競プロの精進記録

アルゴリズム

二項係数 (nCr) の計算方法

AtCoder Grand Contest 025 にて を使う問題が出題されました。いい機会だと思ったので の高速な実装をしてみました。使用言語: C++ 1. なぜ逆元 が必要なのか なので、 が分かれば で が求まります。よって事前に階乗を計算しておけばよいことが分かります。