アルゴリズムは女の子#1
アルゴリズムは女の子#1 アルゴリズムの気持ちがわかりたい. アルゴリズム覚えるだけが増えているので少しメモを書いていきます. お品書き 趣旨は 実装を速攻で書けるように , です. OJ作ったならば実装道場みたいなの作りたいですね. FFT KMP Manacher Z-algorithm ようこそ精進道場へ Warshall-Floyd なんとなくDPなのはわかりますがほぼ暗記するだけみたいなところありますね. k以下の頂点しかない場合の全点対最短路だと考えると, といった感じでしょうか. 間違えないので書きません. FFT これだけで記事一つになりそう… 実際実装するなら毎回導出している時間はないですね. というわけで実装を暗記する,ということも必要ですね. long doubleだと心配なので,NTT, CRTでの復元は使えるようになっておきたいです. 任意modはよくわからないです. 基本 complex<double> で書いてみます. 原始根には e x p ( 2 π i / n ) exp(2 \pi i / n) e x p ( 2 π i / n ) を使います. 高校数学の複素数さえわかればガウス平面で図形的に直行性を感じることができます(また(有限)等比級数の和の公式からも示せます) NTTを考えるにしても,この環が見えているとだいぶ理解しやすいと思います! // a.size() is 2 ^ k vector < comp > fft ( vector < comp > a , bool inverse = false ) { int n = a . size ( ) ; if ( n == 1 ) return a ; vector < comp > a0 ( n / 2 ) , a1 ( n / 2 ) ; for ( int i = 0 ; i < n / 2 ; i ++ ) a0 [ i ] = a [ i * 2 ] , a1 [ i ] = a [ i * 2 + 1 ] ; a0 = fft ( a0 ) ; a1 = ...