0w1

FFT

IOICJ 102 No Title ( FFT )

Problem Description: Given N integers A[ 0, N ), you want to know how many ordered tuples ( i, j, k ) satisfy: 1 ≤ i, j, k ≤ N and A[ i ] + A[ j ] = A[ k ] Constraints: 1≤T≤10 3≤n≤1e5 −50000≤a1,a2,…,an≤50000Sample Input: 3 3 1 2 3 4 2 2 2 …

Fast Fourier Transform

Fast fourier transform can be applied on multiplication of polynomial functions, giving O( N lgN ) time complexity. One of the most common usage is for fast multiplication on big numbers. It exploits the property of the complex roots of un…