Add geometric progressions to an array?

Revision en2, by mohamedeltair, 2019-08-06 01:50:29

I have posted this question before, but I received a comment stating that it is a part of a problem in an ongoing Hackerearth contest, so I deleted it. Since the aforementioned contest ended about 8 days ago, and its editorial is not published yet, I am posting the question again.

If we have an array $$$A$$$ of $$$N$$$ elements, and $$$Q$$$ queries. $$$a_i$$$ and $$$b_i$$$ are given in the $$$i_{th}$$$ query. You are asked to add $$$a_i$$$ to $$$A_0$$$, $$$a_i*b_i$$$ to $$$A_1$$$, $$$a_i*b_i^2$$$ to $$$A_2$$$, ..., $$$a_i*b_i^{N-1}$$$ to $$$A_{N-1}$$$. All calculations are done modulo a prime $$$P$$$, and you are required to print $$$A$$$ after all queries.


$$$1\le N,\, Q\le 2*10^5$$$

$$$1\lt P\lt 2*10^9$$$

$$$1\le a_i,\, b_i\lt P$$$

The previously mentioned problem on Hackerearth: Functions in arrays.

Tags fft, polynomials, math, linear algebra


  Rev. Lang. By When Δ Comment
en2 English mohamedeltair 2019-08-06 01:50:29 33
en1 English mohamedeltair 2019-08-06 01:39:36 938 Initial revision (published)