ps:problems:boj:11385
씽크스몰
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 11385 |
| 문제명 | 씽크스몰 |
| 레벨 | 다이아몬드 3 |
| 분류 |
고속 푸리에 변환 |
| 시간복잡도 | O((n+m)log(n+m)) |
| 인풋사이즈 | n<=1,000,000, m<=1,000,000 |
| 사용한 언어 | Python |
| 제출기록 | 317764KB / 5748ms |
| 최고기록 | 5748ms |
| 해결날짜 | 2021/02/15 |
| 태그 | |
- '씽크스 몰'이 대체 무슨 뜻인지 제목을 이해하는 데 너무 오래 걸렸다. 의도한 것은 '씽크 스몰' 이었던 것 같다..
풀이
- 고속 푸리에 변환 (Fast Fourier Transform, FFT)의 가장 대표적인 활용인 다항식의 곱셈을 그대로 낸 문제.
- 그러나 이 문제의 난이도를 높이는 것은 계수의 값의 범위가 상당히 커지기 때문에 실수 오차가 생길 수 있다는 것. 그래서 정석적인 풀이는 정확도 높은 FFT와 NTT 에서 설명한 것 처럼, 다항식을 두개로 쪼개서 계산하든가 NTT를 사용하든가 하는 방법인것 같다.
- 그치만 여기를 보면, cpp기준 long double을 사용하고, ω_s를 미리 계산하는 식으로만 처리해줘도 통과되는 것 같은데.??
- 뭐 이론은 그렇고.. teflib의 multiply는 이런 실수 오차를 방지하게 되어있는 구현(NTT기반)을 그대로 가져다 쓰는 것이기 때문에, 그냥 이런거 걱정 없이 그냥 쓰면 된다;
- 시간복잡도는 O(nlogn), (n=max(N,M))
코드
(다이아몬드 이상은 코드 첨부 생략)
- Dependency: teflib.fft.multiply
ps/problems/boj/11385.txt · 마지막으로 수정됨: 2021/04/03 11:28 저자 teferi
토론