오늘 문제하나 푸려고 하니까 (1+x^a_i)들의 곱을 계산해야하는 문제가 있더라고

FFT + divide and conquer로 푸려고 하니까 sum(a_i)가 10^9나 되서 풀수가 없었음.

그래서 찾아보니까 #p subset sum이란걸 쓰는거더라 https://judge.yosupo.jp/problem/sharp_p_subset_sum


그래서 저거를 푸려고 식을 봤더니 갑자기 polynomial의 log와 exp를 계산해야하는 부분이 생겼고

https://judge.yosupo.jp/problem/exp_of_formal_power_series

https://judge.yosupo.jp/problem/log_of_formal_power_series


이거를 계산하려고 하니까 polynomial의 inverse를 계산하는 연산이 필요했고

https://judge.yosupo.jp/problem/inv_of_formal_power_series


또 Taylor Series, FFT는 기본에 Newton Method같은것도 나와서 진짜 개빡세게 공부하고

공부 다 하고 저 위에것들을 전부 다 구현하려고 하니까 진짜 멘탈 단단히 터져버림

내가 왜 이걸 하고있나 생각되더라 분명 PS취미인데 이런걸 아득바득 짜서 저장해놓고, 또 저장해놓은 코드 불러와서 추후에 그 문제 맞았다고 해도

그게 즐겁나...? 진짜 취미 맞음...?


결국 inverse of polynomial 하나만 구현하고 손놔버림

진짜 PS 잘하는 사람들 보면 온갖 템플릿 다 구현해놨던데, 어떻게 그걸 다 했을까.........

나중에 보니 그 문제 난이도 앳코더기준 2600밖에 안되서 또 멘탈 터짐

2600이 낮다는건 아닌데 위에것들 전부 다 구현해야하는 미친난이도에 비해서 2600밖에 안된다니 하