読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

FFT

高速フーリエ変換 (FFT)

FFT

再帰型の FFT はやっぱり遅いので、非再帰型の FFT について調べた。『アルゴリズムイントロダクション 第 3 巻』の「多項式と FFT」を参考にしている。多項式の次数は自由度(係数の個数)の意味で使っている。

CodeChef July Challenge 2016: Evaluate the polynomial

https://www.codechef.com/JULY16/problems/POLYEVAL 問題 多項式が与えられるので、x[i] での値を mod 786433 で求めよ。 1≦N, Q≦250,000