### mohamedeltair's blog

By mohamedeltair, history, 5 years ago,

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.

• +13

 » 5 years ago, # |   0 Auto comment: topic has been updated by mohamedeltair (previous revision, new revision, compare).
 » 5 years ago, # | ← Rev. 3 →   +15 So, $A_i = \sum\limits_{j=1}^{Q} a_j b_j^i$? Ok, let's use some generating functions: $F(x)=\sum\limits_{i=1}^N A_i x^i = \sum\limits_{i=1}^N\sum\limits_{j=1}^Q a_j b_j^i x^i = \sum\limits_{j=1}^Q a_j \sum\limits_{i=1}^N (xb_j)^i = \sum\limits_{j=1}^Q a_j\dfrac{xb_j - (xb_j)^{N+1}}{1-xb_j}$ Umgh, not really convenient. Let's sum up not to $N$ but to $\infty$ and take only first $N+1$ terms: $F(x)\equiv\sum\limits_{j=1}^Q \dfrac{a_jb_j x}{1-xb_j}\pmod{x^{N+1}}$ 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)$.
•  » » 5 years ago, # ^ |   0 Thanks a lot.