Блог пользователя mshubham

Yandex Algorithm Qualification Round | Problem D
Автор mshubham, 13 лет назад, По-английски

Infinite Sum

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

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

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.

→ Ответить