FFT1 BOJ 20176 - Needle (FFT) www.acmicpc.net/problem/20176 참고 koosaga.com/263 세 수열 $a,b,c$ 가 주어질 때, $ a_i+c_j=2 * b_k $ 를 만족하는 쌍 $ (i,j,k) $의 개수를 세는 것 x좌표의 범위를 0-60000으로 두고 답을 구하는 식을 만들면 다음과 같다. \[\sum_{x = 0}^{60000} count_b[x] \times \sum_{y = 0}^{2x} (count_a[y] \times count_c[2x-y])\] fft를 이용해서 합성곱을 구할 수 있다. \[conv[i] = \sum_{x = 0}^{i} (count_a[x] \times count_c[i - x])\] 다시 식을 정리하면.. \[\sum_{x = 0}^{60000} (count_b[x].. 2021. 1. 2. 이전 1 다음