전체 글
-
-
Power Projection of Set Power Series알고리즘 2026. 4. 25. 13:10
이 글과 동일한 내용이다.Introduction이 글에서는 power projection of set power series를 $O(N^2 2^N+M)$에 계산하는 알고리즘에 대해 알아볼 것이다. 이를 이용해 정점이 $N$개인 그래프의 chromatic polynomial을 $O(N^2 2^N)$에 계산하는 알고리즘도 함께 다룬다. 이 글에서는 Operations on Set Power Series의 내용을 모두 이해했다고 가정하고 설명한다.Power Projection of Set Power SeriesSet $G = \{ g_0, g_1, \cdots, g_{N-1} \}$과 commutative ring $R$에 대해 정의된 set power series $\mathcal S_G(R)$에 대해 생각..
-
-
-
ACL 기반 다항식 라이브러리알고리즘 2026. 3. 7. 11:01
https://github.com/qwerasdfzxcl/ac-library GitHub - qwerasdfzxcl/ac-library: AtCoder LibraryAtCoder Library. Contribute to qwerasdfzxcl/ac-library development by creating an account on GitHub.github.comatcoder/ext 폴더에 다항식 관련 코드를 작성하고 있다. expander.py에 -x 플래그를 주면 ext 헤더에 있는것만 expand한다. 그냥 돌리면 전부 expand한다. atcoder/convolution 기반이라 ntt가 되면 빠른데 불가능하면 ntt 3번 + crt를 돌려서 조금 느리다.
-
Subset Convolution, Multidimensional Convolution알고리즘 2026. 2. 27. 11:18
Convolution컨볼루션은 기본적으로 다음과 같이 계산한다: 1. $F = FFT(f)$, $G = FFT(g)$를 계산한다.2. $H = F \odot G$를 계산한다. (element-wise product)3. $h = iFFT(H)$를 계산하면 $h$가 답이다. 여기서 FFT를 적절한 변환으로 설정하면 OR convolution, XOR convolution, GCD convolution, LCM convolution을 할 수 있다. 대표적으로, FFT 대신 SOS DP를 돌리면 OR convolution이 된다. 편의상 이러한 변환을 $FFT_{OR}$로 표기하자. Subset Convolution아쉽게도 subset convolution을 $O(n \cdot 2^n)$에 계산할 수 있게 해..
-
2025 회고록일기장 2025. 12. 28. 20:33
PS올해는 특정 기간에만 PS를 했다. 겨울학교와 국대교육 코치를 했고, 국대교육 기간 동안 국가대표 학생들과 같이 문제를 풀면서 PS를 했다. 국대교육을 시작한 6월 초부터 ICPC 서울 리저널이 있었던 11월 말까지 PS를 했고, 그 외의 기간에는 거의 하지 않았다. IOI 코치로 볼리비아에 가게 되었다. 비행기 경유를 3번이나 해야 하는 끔찍한 위치였는데 한국 미국 비행만 좀 힘들었고 나머지는 별로 안 길어서 생각보다 힘들지 않았다. 지금까지 대부분의 IOI는 4금을 딸 확률이 어느 정도 있었지만 항상 실패했기 때문에 올해도 별생각 없었는데 4금을 따서 꽤 놀랐다. 코드포스 레이팅은 많이 떨어졌다.(현재 2567, max 2781) 코드포스 라운드 자체를 많이 안 치기도 했고, 버츄얼도 딱히 안 ..