けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2018-06-08から1日間の記事一覧

よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方

1. 典型的な二項係数の求め方 (1 ≦ k ≦ n ≦ 107 程度) 競プロをしていると、nCk mod. p を計算する場面にしばしば出くわします。時と場合によって色んな方法が考えられますが、以下のものを頻繁に使用するイメージです。多くの AtCoder のトッププレイヤーた…