전체 글
-
a_1, a_2, ..., a_n이 주어졌을 때 a_1^{-1}, a_2^{-1}, ..., a_n^{-1}을 O(n + log mod)에 구하기알고리즘 2026. 9. 24. 12:18
팩토리얼 역원 전처리랑 똑같은 아이디어다. $b = [1, a_1, a_1a_2, \cdots, a_1a_2\cdots a_n]$을 계산하자. 이는 $O(n)$이 걸린다. $c = [1, a_1^{-1}, (a_1a_2)^{-1}, \cdots, (a_1a_2\cdots a_n)^{-1}]$이라고 하면, $c[n] = b[n]^{-1}$이고, $c[i] = c[i+1] \times a_{i+1}$이므로 $c$를 $O(n+\log mod)$에 계산할 수 있다. $a_i^{-1} = b[i-1] \times c[i]$이므로 문제가 해결됐다.
-
f(k)=0^k + 1^k + ... + (n-1)^k일 때 f(0), f(1), ..., f(m-1)을 O(mlogm)에 구하기알고리즘 2026. 9. 24. 12:08
https://qwerasdfzxcl.tistory.com/39 예전에 이런걸 쓴적이 있는데, 그 이후로 이걸 요구하는 문제를 본 적이 없다... 이번 글은 실제로 꽤 많이 쓰이는 알고리즘이다. (백준 1386 f와 g, 2025 마닐라 리저널 K, ARC++ 230 D) 풀이$0^0=1$로 가정한다. EGF로 생각하면 매우 쉽다.$$\begin{align*} g(x) &= \sum_{k=0}^\infty \frac{f(k)}{k!} x^k \\ &= \sum_{k=0}^{\infty} \sum_{i=0}^{n-1} \frac{i^k}{k!}x^k \\ &= \sum_{i=0}^{n-1} \sum_{k=0}^\infty \frac{i^k}{k!}x^k \\ &= \sum_{i=0}^{n-1} e^{ix}..
-
-
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)$에 계산할 수 있게 해..