다항식 연산 알고리즘 정리
다항식 곱셈
두 다항식 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에 게시됨