mohamedeltair's blog

Add geometric progressions to an array?
By mohamedeltair, history, 5 years ago, In English

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.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mohamedeltair (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

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

→ Reply