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

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

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

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

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

http://codeforces.me/blog/entry/4387

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

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

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

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

      2) Головой

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

        Насчет первого пункта дополню, что решение подобных задач детально описано на е-максе в статье про префикс-функцию.

        → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
      ← 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 тебе в помощь по префикс функции, возведению матрицы в степень, и пр.

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

        Спасибо, более менее понятно, попробую на днях реализовать)

        → Ответить