### Hasnaine_'s blog

By Hasnaine_, history, 6 weeks ago, , Summary of the problem: You are given a polynomial $a_0x^0 + a_1x^1 + a_2x^2 + .... + a_nx^n$

Initially, you will be given the values of $a_0, a_1, a_2, a_3 ..... a_n$.

The degree of this polynomial(n) will be at most $200000$.

Then there will be another $200000$ query. In each query, you will receive $x$. You will have to find the value of the polynomial after evaluating with $x$ with $mod$ $786433$. ntt, Comments (3)
•  » » 6 weeks ago, # ^ | ← Rev. 5 →   Thanks a lot for explaining. Though I am spending a lot of time nowadays trying to learn all the details about FFT, there's always remain some confusion.But I have some question though, So, Let's I have the coefficient $a_0, a_1, a_2, a_3 ....... a_n$ of a particular polynomial. Now should I just do divide and conquer here like we do in the FFT and evaluate the polynomial for generator $g$ instead of primitive roots of unity $w_n$? In setter solution and tester solution, they used 3 polynomials of $p(g)$, $p(g^2)$ and $p(g^3)$ to derive the solution where $g$ = generator. What was the use of it? Why not get one single polynomial and derive the whole solution from it? Thanks a lot again.
•  » » Another thing to note:I think they used a generator of $2^k$ as the replacement of the primitive root of unity $w_n$ where given $mod$ is represented as $(2^k * c) + 1$. So what was the use of generator $g$ of prime/mod in the solution?