caiocandido's blog

Solution to Exercise 5.2.5* from Competitive Programming 3rd — (Halim) ?
By caiocandido, history, 9 years ago, In English

Recently I was studying math and came across this problem:

Given 1 < a < 10, 1 <= n <= 100000, show how to compute the value of: 1 * a + 2 * a^2 + 3 * a^3 + ... + n * a^n efficienty, i.e. in O(log n)!

Could someone give ideas/way to solve this problem?

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

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

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it 
Let S = 1 * a + 2 * a^2 + 3 * a^3 + ... + n * a^n   ... i
Then, a*S = 1*a^2 + 2*a^3 + ... + n*a^(n+1)         ... ii
Subtracting ii from i gives :-
(1-a)S = (a + a^2 + ... + a^n) - n*a^(n+1)
S = [(a + a^2 + ... + a^n) - n*a^(n+1)] / (1-a)

x1 = (a + a^2 + ... + a^n) = a*(1-a^(n-1))/(1-a)  (sum of geometric progression), &
x2 = n*a^(n+1)
So, the problem basically reduces to finding x^y which can be solved in O(log y) .
→ Reply
»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

FFT obviously!

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can get the desired series by differentiating the general geometric sum formula and then multiplying both side by a —

Also, this can be helpful somewhere (for example - 908D - New Year and Arbitrary Arrangement) -

→ Reply