코딩은 생각보다 어렵진 않은데
까딱 잘못하면 상수가 커져서 nlogn이여도 TLE나는 경우가 많음.
인터넷에서 보이는 코드들은 최적화되서 TLE 안나는 코드긴 한데 그런건 가독성이 안좋아서 이해하기 힘듬.
다른 알고리즘과 다르게 FFT가 성능과 가독성 동시에 잡는게 유달리 어렵다
까딱 잘못하면 상수가 커져서 nlogn이여도 TLE나는 경우가 많음.
인터넷에서 보이는 코드들은 최적화되서 TLE 안나는 코드긴 한데 그런건 가독성이 안좋아서 이해하기 힘듬.
다른 알고리즘과 다르게 FFT가 성능과 가독성 동시에 잡는게 유달리 어렵다
처음 세그트리 나올때도 비슷한 느낌이었는데 지금 정형화 잘되있는거처럼 나중엔 그냥 정리되서 나올듯
FFT를 iterative하게 짜는건 확실히 이해가 많이 필요하긴 한데 recursive하게 짤 때 push_back 여러번 대신 resize 쓰고 In-place 방식으로 바꾸기만 해도 3배 이상 빨라짐. 물론 In-place Iterative로 짜면 거기서 한 2배 가까이 더빨라지긴 한데 가독성이 ㅋㅋ
오 내가 계속 push_back으로 넣어서 느린거였나? 한번 말해본 방식으로 짜볼게
걍 니가 이해 못해서 가독성 떨어진다는거 아님? 팀노트 유명한것들 구현 충분히 볼만한데 상수큰건 어쩔수없는거고
내 능지가 딸려서 그런것도 있긴 한데 민규당 팀노트에 NTT같은건 진짜 이해 못하겠던데
NTT가 이해 안되는거면 root of unity나 coef->point->coef에 대한게 이해가 부족한걸수도 있고 원시근 자체가 이해 안되는걸수도 있고 NTT는 어려운게 맞아