[B! C][fft] slay-tのブックマーク

slay-t id:slay-t

Cとfftに関するslay-tのブックマーク (2)

[数学・numpy] 高速フーリエ変換(FFT)による畳み込み | maspyのHP
概要「Python で競技プログラミングをやる」の文脈で、高速フーリエ変換を使うための基礎知識を整理します。高速フーリエ変換自体は競技プログラミング以外の文脈でも重要なアルゴリズムですが、そうした需要に応えることは、本記事では想定していません。高速フーリエ変換の詳しいアルゴリズムにはこの記事では触れません（既存の解説が多数ありますし）。代わりにフーリエ変換についての基礎知識について、少し整理しました。ここは、使用言語に関係しない部分です。最低限、Python での実装だけ見たい人は大部分を飛ばしてよいと思います。フーリエ変換の性質フーリエ変換の定義詳しくは、本記事では扱いません。 $K$ を $1$ の $n$ 乗根を $n$ 個持つ体とします（競プロの文脈だと、$K=\C$ および $K=\F_p$ が重要です）。 $K$ に値を持つ数列 $A = (a_0,a_1,\ld
slay-t 2020/09/02
数学

C

math

competitiveprogramming

fft

convert

mathematics
リンク
高速フーリエ変換の実装を難しそうかなと思っている方が、なんだ簡単じゃないですか！！となるための実装講座です - CADDi Tech Blog
対象読者さんはどのような方ですか？ FFT（高速フーリエ変換）の定義を知っているものの、その実装が難しそうだと感じて困っている方々です。逆に原理や有用性、理論的な子細にご興味のある方のご期待には応えられないと思います。目標 FFT に苦手意識のあった方が、最低限動くコードを書くだけなら簡単かも？と感じてくださるまでになれたら、私はとっても嬉しいです。離散フーリエ変換とは定義はウィキペディアにあります。（責任放棄） wikipedia: 離散フーリエ変換今回採用する定義最速で実装までたどり着きたいですから、理論的なところはスキップです。 $N = 2 ^ n$ としましょう。$N$ 次多項式を入れると $N$ 次多項式を返してくれる何かがフーリエ変換です。多項式と言いましたが、コンピュータープログラムですから、係数を並べたものだと思ってくださると嬉しいです。複素係数 $N$ 次
slay-t 2020/03/30
C

blog

tech

math

フーリエ変換

programming contest

fft

algorithm

doc
リンク
1