다항식 연산 알고리즘 정리
다항식 곱셈
두 다항식 F(x)와 G(x)가 주어졌을 때, H(x) = F(x)G(x)를 계산한다.
NTT를 활용해 점값 표현으로 변환한 후 점별 곱셈을 수행하고, 역변환으로 결과를 얻는다. 시간 복잡도는 O(n log n)이다.
void poly_multiply() {
read(n, m);
FOR(i, 0, n) read(f[i]);
FOR(i, 0, m) read(g[i]);
int sz = 1, bit = 0;
while(sz > 1) | ((i & 1 ...
6월 29일 22:19에 게시됨
다항식 연산과 고속 변환 알고리즘
다항식의 빠른 곱셈
두 다항식의 합성곱(convolution)을 계산할 때, 단순한 방법은 모든 항을 직접 곱하는 것으로 시간 복잡도는 $O(n^2)$이다. 하지만 $O(n \log n)$ 시간에 이를 수행할 수 있는 알고리즘이 존재하는데, 대표적으로 FFT(고속 푸리에 변환)와 NTT(수론적 변환)가 있다. 이들은 본질적으로 DFT(이산 푸리에 변환)와 IDFT(역 이산 푸리에 변환)를 효율적으로 ...
6월 18일 19:50에 게시됨