W4yneb0t's blog

Linear recursion problem — help me find it
By W4yneb0t, history, 7 years ago, In English

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.

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

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Is it Kyoya and Train's solution?

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

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Jetpack was the one I'm looking for, thanks!

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

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I saw you wrote a very detailed editorial. It must have taken lots of time.

    Compliments.

    → Reply