BOJ 1067 이동

FFT 기본 유형 문제 중 하나입니다. 다음과 같은 방법으로 FFT를 사용하여 $\mathcal{O} (n \log n)$ 시간에 필요한 모든 값을 구할 수 있습니다.

예시로 $n = 4$라고 하고, 두 다항식 $x_0 + x_1 x + x_2 x^2 + x_3 x^3$과 $y_3 + y_2 x + y_1 x^2 + y_0 x^3$을 곱하면 다음을 얻습니다. ($y$의 계수의 순서를 뒤집었음에 유의합니다.)

$$ x_0 y_3 + (x_0 y_2 + x_1 y_3) x + (x_0 y_1 + x_1 y_2 + x_2 y_3) x^2 + (x_0 y_0 + x_1 y_1 + x_2 y_2 + x_3 y_3) x^3 \

• (x_1 y_0 + x_2 y_1 + x_3 y_2) x^4 + (x_2 y_0 + x_3 y_1) x^5 + x_3 y_0 x^6 $$

이제 차수가 $n$ 차이가 나는 항들을 묶어서 더해주면 원하는 $n$개의 이동에 대한 결과값들을 모두 얻을 수 있습니다. 이제 이들 중에서 최댓값을 출력하면 됩니다.