사용자 도구

사이트 도구


ps:problems:boj:11385

씽크스몰

ps
링크https://www.acmicpc.net/problem/11385
출처BOJ
문제 번호11385
문제명씽크스몰
레벨다이아몬드 3
분류

고속 푸리에 변환

시간복잡도O((n+m)log(n+m))
인풋사이즈n<=1,000,000, m<=1,000,000
사용한 언어Python
제출기록317764KB / 5748ms
최고기록5748ms
해결날짜2021/02/15
태그

Class 9 Essential

  • '씽크스 몰'이 대체 무슨 뜻인지 제목을 이해하는 데 너무 오래 걸렸다. 의도한 것은 '씽크 스몰' 이었던 것 같다..

풀이

  • 고속 푸리에 변환 (Fast Fourier Transform, FFT)의 가장 대표적인 활용인 다항식의 곱셈을 그대로 낸 문제.
  • 그러나 이 문제의 난이도를 높이는 것은 계수의 값의 범위가 상당히 커지기 때문에 실수 오차가 생길 수 있다는 것. 그래서 정석적인 풀이는 정확도 높은 FFT와 NTT 에서 설명한 것 처럼, 다항식을 두개로 쪼개서 계산하든가 NTT를 사용하든가 하는 방법인것 같다.
    • 그치만 여기를 보면, cpp기준 long double을 사용하고, ω_s를 미리 계산하는 식으로만 처리해줘도 통과되는 것 같은데.??
  • 뭐 이론은 그렇고.. teflib의 multiply는 이런 실수 오차를 방지하게 되어있는 구현(NTT기반)을 그대로 가져다 쓰는 것이기 때문에, 그냥 이런거 걱정 없이 그냥 쓰면 된다;
  • 시간복잡도는 O(nlogn), (n=max(N,M))

코드

(다이아몬드 이상은 코드 첨부 생략)

토론

댓글을 입력하세요:
J​ Q A D R
 
ps/problems/boj/11385.txt · 마지막으로 수정됨: 2021/04/03 11:28 저자 teferi