サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
ドラクエ3
sen-comp.hatenablog.com
この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$ 10 ^ 9 + 7 $じゃダメなのか 原始根って何？ とかについてもこれを見ればわかります。 前提知識としては、Fast Fourier Translation(高速フーリエ変換)が必要です。 kaage大先生のQiita記事とかは中高生にもわかりやすく書かれています。 下に一応自分の勉強ノートを載せます。(上の記事の行間を埋めた感じです) では、数論変換について説明したいと思います。 高速フーリエ変換の弱点 高速フーリエ変換は正しいですが、弱点として精度が足りないというのがあります。 なぜならば、複素数の1の$ 2 ^ m $乗根は計算上ではれっきとした64bit倍精度浮動小数点
新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。 そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。 以下のページ、PDFを参考にしてます。 snuke.hatenablog.com 文字列アルゴリズム from HCPC: 北海道大学競技プログラミングサークル www.slideshare.net Z-algorithmで何ができるか？ 文字列Sに対して、S[i : j]という記号を、Sのi番目からj番目(いずれも0-idx)までの連続部分文字列とします。 例えば、S="abcde"で S[1 :
このページを最初にブックマークしてみませんか？
『Senの競技プログラミング備忘録』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
