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

Помогите решить задачу
Автор Battle_Mage, 14 лет назад, По-русски

Просьба кому-нибудь, кто решил эту задачу — проведите разбор. Заранее спасибо.

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

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

http://mirror.codeforces.com/blog/entry/4387

→ Ответить
  • »
    »
    14 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    Спасибо за ссылку, но я всё-равно не могу понять: 1) Рассматривая случай, "что они пересекают разрез на стыке fk - 1 и fk - 2." — как мы рассматриваем данный случай? Допустим строка у нас длиной 10^5 — придётся рассматривать 10^5 вариантов разбиения строки на 2 и их вхождения? 2) "Далее нужно вычислить рекурентность." — как это сделать?

    → Ответить
    • »
      »
      »
      14 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      1) Префикс-функцией

      2) Головой

      → Ответить
    • »
      »
      »
      14 лет назад, скрыть # ^ |
      ← Rev. 4  
      Проголосовать: нравится +1 Проголосовать: не нравится

      1) разбиения строки на две? у нас строка f[i] = f[i — 1] + f[i — 2] т.е. две строки склеенные, у нас есть одно разбиеные а не 10^5, теперь найдем все вхождения строки s в f[i] такие что строка s пересекает место склейки (вот таких может быть порядка 10^5, но все равно это легко вычисляется хешами/префикс функцией)
      2) "Далее нужно вычислить рекурентность." другими словами "теперь нужно применить заданную в первой строке формулу к нашему данному в инпуте k" Для 30 баллов можно тупо в цикле все посчитать. Поскольку формула линейная, можно её считать возведением матрицы в степень, это стандартный подход, см например задачу о находнениии n-го числа фиббоначчи за O(log(n)). e-maxx.ru тебе в помощь по префикс функции, возведению матрицы в степень, и пр.

      → Ответить