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

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

===== 코드 =====
(다이아몬드 이상은 코드 첨부 생략)
  * Dependency: [[:ps:teflib:fft#multiply|teflib.fft.multiply]]

{{tag>BOJ ps:problems:boj:다이아몬드_3}}