[B! fft] drunkturtleのブックマーク

NTT(数論変換)のやさしい解説 - Senの競技プログラミング備忘録

この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。あまりなかったので書きました。数論変換にありがちななんで$ 10 ^ 9 + 7 $じゃダメなのか原始根って何？とかについてもこれを見ればわかります。前提知識としては、Fast Fourier Translation(高速フーリエ変換)が必要です。 kaage大先生のQiita記事とかは中高生にもわかりやすく書かれています。下に一応自分の勉強ノートを載せます。(上の記事の行間を埋めた感じです) では、数論変換について説明したいと思います。高速フーリエ変換の弱点高速フーリエ変換は正しいですが、弱点として精度が足りないというのがあります。なぜならば、複素数の1の$ 2 ^ m $乗根は計算上ではれっきとした64bit倍精度浮動小数点

drunkturtle 2021/10/12

fft

リンク

FFT:NTT

2020/07/13 HCPC 2020/07/13 HCPC /46 !2 2020/07/13 HCPC /46 f(x) n − 1 ζn 1 n 𝒪(n2 ) 𝒪(n log n) !3 ̂ f(t) = n−1 ∑ i=0 f(ζi n)ti 2020/07/13 HCPC /46 !4 2020/07/13 HCPC /46 (x + x2 + x4 )(x3 + x6 + x10 + x15 )[x7 ] = 2 f(x)[xa ] := xa !5 2020/07/13 HCPC /46 f(x), g(x) n m f(x)g(x) n + m − 1 f(x) = (1 + 2x) g(x) = (3 + x + 4x2 ) f(x)g(x) = 3 + 7x + 6x2 + 8x3 !6 2020/07/13 HCPC /46 !7 f(x), g(x) n m