Просьба кому-нибудь, кто решил эту задачу — проведите разбор. Заранее спасибо.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 159 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 150 |
| 6 | atcoder_official | 148 |
| 6 | SecondThread | 148 |
| 8 | nor | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.07.2024 02:52:03 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
http://mirror.codeforces.com/blog/entry/4387
Спасибо за ссылку, но я всё-равно не могу понять: 1) Рассматривая случай, "что они пересекают разрез на стыке fk - 1 и fk - 2." — как мы рассматриваем данный случай? Допустим строка у нас длиной 10^5 — придётся рассматривать 10^5 вариантов разбиения строки на 2 и их вхождения? 2) "Далее нужно вычислить рекурентность." — как это сделать?
1) Префикс-функцией
2) Головой
Насчет первого пункта дополню, что решение подобных задач детально описано на е-максе в статье про префикс-функцию.
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 тебе в помощь по префикс функции, возведению матрицы в степень, и пр.
Спасибо, более менее понятно, попробую на днях реализовать)