Add Fast Fourier Transform (FFT)

[TimmyChiang]

Introduction to Fast Fourier Transform (FFT)

Mathematical Background

• The principal nth root of unity
• Representing polynomials
  • Coefficient representation
  • Point-value representation
• Vandermonde matrix and its properties

DFT && Inverse DFT

• Introduction
• Calculation (by Vandermonde matrix)

FFT algorithm

• Find DFT
• Divide and conquer
• Find Inverse DFT

Exercises

• Easy
  • SPOJ Polynomial Multiplication [3]
• Medium
  • SPOJ Maximum Self-Matching [4]
  • SPOJ Ada and Nucleobase [5]
  • Codeforces Yet Another String Matching Problem [6]
  • Codeforces Lightsabers (hard) [7]
  • Codeforces Running Competition [8]
  • Codeforces Dasha and cyclic table [9]
  • Kattis A+B Problem [10]
  • Kattis K-Inversions [11]

References

• [1] Introduction to Algorithms Fourth Edition p. 877 ~ p. 893
• [2] CP Algorithm, Fast Fourier transform https://cp-algorithms.com/algebra/fft.html
• [3] https://www.spoj.com/problems/POLYMUL/
• [4] https://www.spoj.com/problems/MAXMATCH/
• [5] https://www.spoj.com/problems/ADAMATCH/
• [6] https://codeforces.com/problemset/problem/954/I
• [7] https://codeforces.com/problemset/problem/958/F3
• [8] https://codeforces.com/contest/1398/problem/G
• [9] https://codeforces.com/contest/754/problem/E
• [10] https://open.kattis.com/problems/aplusb
• [11] https://open.kattis.com/problems/kinversions