지금까지 고속푸리에변환(이하 FFT)의 원리를 잘 모르고 썼는데 오늘 각잡고 공부해서 깨달았다. 아직 완벽히 이해한건 아닌것 같지만 잊어버리기 전에 남겨놓고자 한다. (쓰다보니 길어져서 파트를 나누었다. part1은 필요한 지식, part2에 FFT 원리에 대해 포스팅한다.) 감사한 곳 https://codeforces.com/blog/entry/43499 https://codeforces.com/blog/entry/43499 codeforces.com FFT는 다항식을 빠르게 계산하는 알고리즘이다. $A(x) = \sum_{i=0}^{n-1} a_ix^i, B(x) = \sum_{i=0}^{n-1} b_ix^i$일 때 $C(x)=A(x)B(x)$를 빠르게 구하는 알고리즘이다. 그냥 단순 알고리즘으로 구..