競プロでよく使われる組み合わせアルゴリズムの意味がよくわからない人に送るまとめ

しゅういち(虚無) @hideh_1231

@tempura_pp それとフェルマーの小定理を合わせるんですね、なるほど でも指数のpは素数じゃなければならないっていうやつは大丈夫なんですか…？

てんぷら @tempura_cpp

@hideh_1231 それはめっちゃそうで、実はけんちょんさんの方もこっちもmodが素数じゃないと使えません と言ってもよくでてくる1e9+7と998244353(だっけ)はどっちも素数なのでだいたい使えます

てんぷら @tempura_cpp

@hideh_1231 modが素数じゃない環境で二項係数を求める場合には、パスカルの三角形の、nCk=(n-1)Ck+(n-1)C(k-1)を利用して再帰で計算するのがいいと思います(計算量はO(N^2)です)。 modが素数じゃなくてかつO(N^2)が間に合わない問題はでません(無理なので)

しゅういち(虚無) @hideh_1231

@tempura_pp そうなんですね…！ けんちょんさんの方(拡張ユークリッド？)も素数じゃなきゃダメなんですね…

てんぷら @tempura_cpp

@hideh_1231 そもそも素数じゃないと逆元の存在が保証されないですからね、、、 (たとえばmod6で2に対する逆元は存在しない)(何をかけても偶数になって1になりえないことからわかる)