FFT에 대해 모른다면 FFT를 먼저 공부하고 오자. Fourier Transform을 보는 다양한 관점으로는 기저변환행렬, 보간법, 주파수 분해 등이 있으며, 특히 이산 푸리에 변환(DFT)를 빠르게 하는 알고리즘을 FFT(Fast Fourier Transform)이라 부른다.

FFT, 특히 정수 primitive root of unity(원시근)을 이용한 FFT인 NTT를 이용하는 문제이다.

14882번: 다항식과 쿼리

Baekjoon Online Judge스타트링크 (Startlink)

원시근이란?

$a^x =1 \mod n$인 최소의 $x>0$이 $x=\phi(n)$, 특히 $n$이 소수일 때 $x=\phi(n)=n-1$를 만족하면 이러한 $a$를 법 $n$에 대한 원시근이라 한다.

NTT란?

Number Theoretic Transform, NTT는 FFT에서 사용하던 복소수 원시근("복소수 원시근"이라는 표현이 정확한지는 모르겠다.) $w=e^{2\pi \frac{1}{N}}$ 대신 정수 원시근을 사용해 FFT를 돌리는 방법이다.

이는 원시근 $a$에 대해 $a^0, a^1, \cdots, a^{n-2}$이 모두 다름을 이용해 $f(a^0), f(a^1), f(a^2), \cdots f(a^{n-2})$을 분할정복을 이용해 $O(N\log{N})$만에 구한다. 역변환 또한 FFT에서 했던 것과 똑같이 하면 되지만, 상술한 문제에서는 역변환이 필요 없다.

문제 풀이

문제의 제약 조건 중, 수가 786433보다 작다는 조건이 있는데 786433은 $3 \cdot 2^{18}+1$인 소수이다. 즉 $MOD-1$은 Cooley–Tukey 알고리즘으로 18번 분할이 가능하고, $MOD$는 원시근으로 10, 11, 13 등을 갖는다. (원시근은 브루트포스를 통해 찾았으나, baby-step giant-step을 통해 $\sqrt{N}$의 복잡도로 찾을 수 있다. 원시근은 하나 $a$만 찾으면 $a^k$(단, $gcd(k, \phi(N))=1$)이 모두 원시근이 되므로 하나만 찾으면 충분하다.)

아무튼 이러한 정수 원시근을 이용해 FFT를 돌려 $f(w^0), f(w^1), \cdots , f(w^{N-2})$을 계산하면 $1$부터 $MOD-1$까지 모든 수에 대해 $f(x)$값을 $O(N\log{N})$ 시간만에 구해낼 수 있다. $x=0$에 대해서만 예외처리하여 결과를 출력하면 된다.

풀이에서 $MOD$와 $N$을 혼용하여 썼음에 유의