Doubt Regarding NTT

Правка en1, от manjunath1996, 2017-03-17 14:08:18

I have a doubt about how devide polynomial in NTT.Specifically in this problem link :https://www.codechef.com/JULY16/problems/POLYEVAL/ In editorial and many solution,they are deviding polynomial into 3 polynomials as A(x^3)+xA(x^3)+x^2A(x^3). I didn't understand why it is needed to devide the polynomial into 3 polynomial first and then apply NTT. Can we take whole polynomial into single array and do it's NTT.Please Clarify my doubt.

Теги ntt, polynomials, fast multiplication

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский manjunath1996 2017-03-17 14:08:18 464 Initial revision (published)