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

Автор Deemo, история, 8 лет назад, По-английски

Can anyone tell me how to solve this problem?

http://mirror.codeforces.com/contest/177/problem/G2

Thanks in advance!

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

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

This is enhanced version of one problem in ICPC WF 2012: https://icpc.kattis.com/problems/fibonacci

Short editorial for WF 2012: http://www.csc.kth.se/~austrin/icpc/finals2012solutions.pdf

I "guess" matrix exponentiation will do the trick for enhanced version (unproven for now, I didn't have time to analyse further).

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

Let's calculate for each prefix s[1..i] the minimum fibonacci index minind[i] such that s[1..i] is a suffix of fib[i] and s[i + 1..n] is a prefix of fib[i + 1].

Because the relation

fib[i] = fib[i - 1]fib[i - 2]

can be written equivalently as:

fib[i] = fib[i - 2]fib[i - 3]fib[i - 2]

it follows that $min_ind[i]$ is either or less than n (because fib[i] has all the prefixes of fib[i - 2]). After that, it is essentially a linear reccurence of type

DP[i] = DP[i - 1] + DP[i - 2] + occurences_less_than_inf

for all $\i \geq n$ (or n + 2 or smth.).

You basically have to compute DP[n] and DP[n + 1] and occurences_less_than_inf, and then do matrix exp. I think that should work :).