FFT in competitive programming
다항식 찾기 (n+1)개의 점, 즉 $(x_i, y_i)$의 순서쌍이 (n+1)개 주어지면, 이 n개의 점을 모두 지나는 다항식을 하나 찾을 수 있다. 즉 $P(x_i) = y_i$를 모두 만족하는 $P(x)$를 찾을 수 있다. (일단 각각의 $x_i$는 모두 다르다고 하자.) 예를 들어 (1, 1)과 (2, 3)을 지나는 다항식은 $f(x)=2x-1$도 있고, $g(x)=x^2-x+1$도 있다. 이런 다항식은 여러 가지가 있고, 무한히 많다. 그런데 사실은, 그중 차수가 가장 낮은 건 n차이고, 게다가 이때의 n차 다항식은 무려 유일하다. 다항식을 왜 찾을까? ― 다항식 곱셈 문제 잠깐 다른 얘기를 해본다. 두 다항식의 곱을 계산하는 문제를 생각하자. 예를 들면 $(x^2 + x + 3)$과 $(x -..
2015. 7. 18. 02:15