백준 10531번 문제 링크
문제 이름 : Golf Bot
주 언어 : Python
태그 : 수학 / 고속 푸리에 변환
solved.ac 등급 : Platinum I (2024/12/06 확인)
백준 10531번 문제 보기
문제 :
(축약 & 번역) - 골프 기계는 골프공을 $N$개의 거리 $k_{0}, k_{1}, \cdots, k_{N - 1}$ 중 한 개의 거리만큼 샷을 날릴 수 있습니다.
골프장에 홀 $M$개가 있고, 골프 기계로부터 거리가 각각 $d_{0}, d_{1}, \cdots, d_{M - 1}$ 만큼 떨어진 곳에 홀이 있습니다.
두 번 이하의 샷을 쳤을 때, 골프 기계는 몇개의 홀에 골프공을 넣을 수 있는지 출력하세요.
※ 공은 계속 한 방향으로만 날아가고 뒤로 날릴 수 없습니다.
입력 :
(축약 & 번역) - 첫 줄에 $N$이 주어지고, 그 다음 $N$개의 줄에 $k_{i}$가 주어집니다.
그 다음 줄에 $M$이 주어지고, 그 다음 $M$개의 줄에 $d_{i}$가 주어집니다.
($1 \leq N, M, k_{i}, d_{i} \leq 200000$)
출력 :
(축약 & 번역) - 골프 기계는 몇개의 홀에 골프공을 넣을 수 있는지 출력하세요.
$d_{t} = k_{i}$ 이거나 $d_{t} = k_{i} + k_{j}$를 만족하는 $(i, j)$가 있어야 합니다.
편의상 $k_{N} = 0$이라 하면 $d_{t} = k_{i} + k_{j}$를 만족하는 $(i, j)$가 있어야 합니다. $(0 \leq i, j \leq N)$
다항식 $g(x)$에 대하여 $[x^{k}]g(x)$를 $g$의 $k$차항의 계수라 하고, $[x^{k_{i}}]g(x) = 1 \, (0 \leq i \leq N)$이라 정의해보겠습니다.
$G(x) = g(x) \times g(x)$라 하면 $(0 \leq i, j \leq N)$인 $i, j$에 대해 $[x^{k_{i} + k_{j}}]G(x) > 0$임을 알 수 있습니다. ($j = N$일 때 $[x^{k_{i} + k_{N}}]G(x) = [x^{k_{i} + 0}]G(x) > 0$도 성립합니다.)
$k_{i} + k_{j}$꼴로 나타낼 수 없는 $d$에 대해서는 $[x^{d}]G(x) = 0$입니다. ($[x^{d}]G(x) \not= 0$이었다면 어떤 수 $a, b$에 대해 $[x^{a}]g(x) = 1$, $[x^{b}]g(x) = 1$ 이었어야만 합니다.)
그렇다면 다항식 $G(x) = g(x) \times g(x)$를 구하면 되니 고속 푸리에 변환 을 이용하여 $G(x)$를 구해줍니다.
10531번 문제는 다음과 같이 풀 수 있습니다.
1. 리스트 $g$를 설정, 입력된 $k_{i}$들에 대해 $g[k_{i}] = 1$로 설정, 특히 $g[0] = 1$로 설정
2. $g$를 다항식으로 보고 $G = g^{2}$를 FFT로 구하기
3. 입력되는 $d_{i}$들에 대해 $[x^{d_{i}}]G(x) > 0$인 개수 세기
길이가 최대 $200000$이니 다항식 차수도 $200000$이고, $G(x)$는 $400000$차 함수까지 될 수 있으니 40만보다 큰 2의 제곱수인 $2^{19} = 524288$을 길이로 잡아줍니다.
-번째 푼 문제 (2022/--/--)