씽크스몰

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

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

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

• Dependency: teflib.fft.multiply