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.
Constraints:
$$$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.
Auto comment: topic has been updated by mohamedeltair (previous revision, new revision, compare).
So, $$$A_i = \sum\limits_{j=1}^{Q} a_j b_j^i$$$? Ok, let's use some generating functions:
Umgh, not really convenient. Let's sum up not to $$$N$$$ but to $$$\infty$$$ and take only first $$$N+1$$$ terms:
Now that's something! I believe we may calculate $$$\sum\limits_{j=1}^Q \dfrac{a_jb_jx}{1-xb_j}$$$ as the rational function $$$F(x) = \dfrac{A(x)}{B(x)}$$$ explicitly with divide and conquer in $$$O(Q \log^2 Q)$$$. Only thing which would be left to do afterwards is to calculate first $$$N+1$$$ terms of $$$B^{-1}(x)$$$ in $$$O(N \log N)$$$ and multiply them with $$$A(x)$$$ to recover $$$F(x)$$$. So, the whole complexity is $$$O(Q \log^2 Q + N \log N)$$$.
Thanks a lot.