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.

Tags ntt, #codechef


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