Need help on a NTT problem

Revision en2, by Hasnaine_, 2020-07-06 06:04:32

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$.

Problem Link: Codechef Polyeval

Note: There is an editorial about this problem. But in that editorial, setter mostly discussed about the details of FFT rather than the details of the problem. Or I might be missing the whole point. So, can you please help me here? :(

Thanks a lot. I would be obliged.

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 Hasnaine_ 2020-07-06 06:04:32 24
en1 Hasnaine_ 2020-07-06 06:03:58 783 Initial revision (published)