mshubham's blog

Yandex Algorithm Qualification Round | Problem D
By mshubham, 13 years ago, In English

Infinite Sum

Can anyone explain the solution.. solution are posted on homepage, but it seems difficult to understand.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
13 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

Let . Then the answer to the problem is (except for the case b = 1 where the sum is infinite). So we want to compute Fa(x).

We see that . Hence, Fa + 1(x) = xF'a(x).

We have . Then , and so on. It's easy to see that , where Pa is a polynomial of degree a. Substituting this expression into recurrent equation for Fa we get

Pa + 1(x) = xP'a(x)(1 - x) + (a + 1)xPa(x).

So we can compute the polynomial Pa using this recurrent equation.

→ Reply