문제 링크
- http://icpc.me/10531
문제 출처
- 2014 SWERC C번
사용 알고리즘
- FFT
시간복잡도
- O(N log N)
풀이
N개의 자연수로 구성된 수열 K가 주어졌을 때, 수열 K의 서로 다른 2개의 숫자를 더해서 Dj를 만들 수 있는지 판별해야 합니다.
수열 K의 각 요소들은 최대 20만이므로 뜬금없지만 20만차 다항식을 만들어봅시다.
수열 K의 요소 중 v가 있다면, v차항의 계수를 1로 지정해봅시다.
위에서 만든 20만차 다항식을 제곱해서 나온 다항식을 보면, 어떤 항의 계수는 0이고, 어떤 항의 계수는 0이 아닙니다.
수열 K의 서로 다른 2개의 숫자를 더해서 v를 만들 수 있다면, v차항의 계수가 0이 아닙니다.
직접 손으로 계산해보면 이유를 알 수 있습니다.
전체 코드
1 |
|