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

Linear recursion problem — help me find it
Автор W4yneb0t, история, 8 лет назад, По-английски

I remember reading this problem in some contest, but I don't remember where. I think the contest was 2016 or so. I searched on a few websites with no luck. Do you happen to know what contest it was?

The problem is: Given integers a1, ..., an, We define x0 = 1 and for every . Find xn. The solution was O(n * polylog(n)) with FFT.

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

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Is it Kyoya and Train's solution?

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

I remember 2 such problems from CSacademy: Colored Forests and Jetpack. Both are basically some easy combinatorics + what you're asking for.

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

I wrote this task on Codechef as well (late 2014): task / solution (It is like O(n log^2 n))

→ Ответить