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

しゅういち(虚無) @hideh_1231

えっ、本当昨日のやつの組み合わせのライブラリのやつの意味がよくわからないんですが

てんぷら @tempura_cpp

@hideh_1231 どのあたりですか(僕が見て分かればですが)(数学的なことはわかると思うけどプログラミング的なことなら分からない)

しゅういち(虚無) @hideh_1231

@tempura_pp けんちょんさんのブログのB問題の解法見てたんですけど、1/n!がどうしてああなっているのかよくわからないのです…

てんぷら @tempura_cpp

@hideh_1231 とりあえずmod11で7の逆元を考えてみましょうか。 逆元を求める作業がかけて1になる、つまり7*xを11で割ったあまりが1になるようなxを求める作業だというのはよいですか

てんぷら @tempura_cpp

@hideh_1231 あぁ申し訳ない(どこから分からないかを雑に探索しようとしていました) なんしか、 7xを11で割ったあまりが1、つまり 7x=11y+1 と表せるようなx,yを求めればいいわけです

てんぷら @tempura_cpp

@hideh_1231 数字が大きい2数に対して求めるのは難しいのでちょっと工夫をします。具体的には11を7で割った余りが4、つまり11=7+4から7=11-4と書けることを使うと、上の問題は (11-4)x=11y+1 つまり、 4(-x)=11(y-x)+1 と書き換えることが出来ます

てんぷら @tempura_cpp

@hideh_1231 では進めます。書き換えた式をよく眺めると、これは｢-xが4の逆元である｣という式になっています。 ということで-x=inv[4]=3 x=-inv[4]=-3 ただしxは0～10の範囲で考えたいので-3を11で割った余りをとって8になります(実際に7*8=56は11で割るとあまり1)

てんぷら @tempura_cpp

@hideh_1231 同じくmod11で4の逆元を考えると 4x=11y+1 となるので11=4*2+3なことを使いたいです。そこでもとの式を2倍して、 4*2x=11*2y+2 (11-3)x=22y+2 3(-x)=11(2y-x)+2 と書き換えます。

てんぷら @tempura_cpp

@hideh_1231 このとき、-xは、｢3の逆元を2倍したもの｣になります。(雑に説明すると逆元はかけて1になるものなんだから、かけて2になるものは逆元を2倍しとけばいいよねってことです) ということで -x=2*inv[3] x=-2*inv[3] となり最後に11で余りをとって0～10の範囲に収めれば完成です

てんぷら @tempura_cpp

@hideh_1231 ちょっとしたポイントとしては、余りをとっているためどちらの例でも小さい数に帰着できているというところです(7→4、4→3) けんちょんさんの実装だと前から順番に計算しているのでinv[4]を計算したいときにはすでにinv[3]は計算されていて、それをそのまま使うことができています

てんぷら @tempura_cpp

@hideh_1231 (あとはたぶん今の議論を全部文字を置いてやるとできるはず)(2つめの例だとmod=11、i=4、mod%i=3、mod/i=2 がそれぞれ対応する)

しゅういち(虚無) @hideh_1231

@tempura_pp ここの-x=inv[4]=3は自分で適当な値である3を置いたら、ってことですよね？ (添字の逆元)=inv[(添字)]を満たすって感じですかなるほど

てんぷら @tempura_cpp

@hideh_1231 そこのinv[4]=3は勝手に書いちゃったんですが、逆元を求めるのをfor文で順番に求めるように書くとinv[7]を計算する時点では0～6までのinvは分かっているのでinv[4]=3も求まっている状態ではあります。

しゅういち(虚無) @hideh_1231

@tempura_pp やってることはわかるんですけど、どうしてそのような操作をしているのかというのがうまく飲み込めずわからないです…すみません… また、それと1/n!の間にどのような関係があるのかもわからなくて…すみません…

てんぷら @tempura_cpp

@hideh_1231 1つめから答えます。 素朴に逆元を求めようとすると7*1、7*2、7*3、、、と順番に試せば見つかるのですが、1～nの逆元全てを知るにはO(n*Mod)かかってしまい、とても間に合いません。そこで前の結果を利用することでO(n)まで計算量を減らしています。

てんぷら @tempura_cpp

@hideh_1231 全然違う方法として、 n^(p-1)をpで割った余り=1 という定理(フェルマーの小定理)があります。 これをn*n^(p-2)≡1だと思うとn^(p-2)がnの逆元だということが分かるので繰り返し2乗法でn^(p-2)を計算することでnの逆元を求めることができます

てんぷら @tempura_cpp

@hideh_1231 僕はこっちのほうが感覚的でわかりやすいのでこっちを使うことのほうが多いです(計算量も1回あたりO(log(Mod))なので十分高速) ただけんちょんさんの実装のほうがlog1個分優秀ではあります なんしか、愚直に探索するとダメだから何かしら工夫をしなきゃいけないね、ということです

しゅういち(虚無) @hideh_1231

@tempura_pp たしかにこちらだと定理でそうだし、って感じでやりやすそうですね… それのライブラリって競プロSlackで31536000さんが上げてたやつのやり方ですかね？コードの途中でビット演算あって思考停止しました(白目) 計算量の都合で両方わかった方がいい感じですかね… 愚直は200までってことはわかりました

てんぷら @tempura_cpp

@hideh_1231 けんちょんさん側の方法は、余りをとると割る数よりも小さくなるっていう性質を使っていて、その部分はユークリッドの互除法(最大公約数を求めるあれ)と同じなんですがそれを加味しても難しいですよね、、、 逆元を求めたいのは数学の人の性なので天才的解法があるのは仕方がない気がします()

てんぷら @tempura_cpp

@hideh_1231 まぁけんちょんさん側の解法じゃないと間に合わない問題に遭遇したことはないので無理に理解する必要もない気はします。 繰り返し2乗法はそれです。こっちは素直にa^bを計算したい時とかにも使うのでできるようにしたいですね。

てんぷら @tempura_cpp

@hideh_1231 bit演算っぽく書いてるので慣れてないとわかりにくく見えますが、やってることは簡単で、 たとえばa^50を計算したいなら a^25を計算して2乗すればいい a^25を計算するためにはa^12の2乗にもう1個aをかければいい a^12を計算するにはa^6を2乗すればいい ……っていうのを再帰で書いてるだけです

てんぷら @tempura_cpp

@hideh_1231 この方法だと1回ごとに指数が半分になるのでa^bをO(log(b))くらいで計算できるので、素朴にかけていくO(b)よりはかなり速くなります