그냥 대부분의 문제에서 무지 짱큰 N에 대해 a_i b_j 합 구한다는 거 말곤 없는건가?
트릭같은 것도 별로 없고?
[질문] FFT는 ps에서 그냥 합성곱 n log n 그 이상 이하도 아닌건가
익명(27.35)
2021-10-29 08:31
추천 1
댓글 8
다른 게시글
-
실시간 피붕이... 좆될뻔했다... [2][일반] Glacier(yoooo9) | 21.10.29추천 0
-
피린이 뻘짓했다 [3][일반] 익명(185.92) | 21.10.29추천 0
-
옛날에 피시방에서 코드포스 한적 있었는데 [1][일반] ㅁ(119.202) | 21.10.29추천 11
-
PC방에 코포하러가면 예쁜 알바누나가 말걸러 옴 [1][일기] EN_SA(encludingsalt) | 21.10.29추천 1
-
pc방에서 PS하면 멋있게 보이려나? [9][일반] 익명(14.52) | 21.10.29추천 4
-
야발!!!!!!!! 풀었다!! 풀었다고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ [4][일반] 익명(175.196) | 21.10.28추천 7
-
손으론 할줄 아는데 코드로 구현을 못하면 뭐가 문제임? [2][일반] 익명(218.39) | 21.10.28추천 0
-
네비게이션에 알고리즘 뭐쓰일까 [3][일반] 익명(175.223) | 21.10.28추천 0
-
플3 찍었다 [12][일반] 익명(110.76) | 21.10.28추천 5
-
브루트 포스 문제 이렇게 푸는거 맞지? [5][일반] 익명(115.95) | 21.10.28추천 16
원리를 이해해야 되는 문제들이 아주 가끔씩은 나옴. 어쨌든 트릭이 별로 없다는 얘기는 어느정도는 맞는말이라고 봄
거의 대부분 그런듯
NTT, FWHT, 비트합성곱 같은거까진 복붙한다고 쳐도 세그로 FFT분할정복 메모하는 문제는 FFT를 이해해야 가능하지 않으려나? 본인은 앞에써둔거 하나도 몰라 걍 뇌피셜임
뭐 별다른 수학적 성질 없이 분할정복을 통한 interpolating이란 원리는 안 바뀌나보네 다들 답변 고마웡
가끔 응용판으로 Multidimensional FFT나 Fast Hadamard Transform정도가 나오긴 하지맘 본질은 너말이 맞음
짜잘한 트릭으로는 NTT할때 FFT-Nonfriendly한 소수가 주어질때(예:10억7) 어떻게 하느냐 등이 있는데 이건 내가 잘 모름