Просьба кому-нибудь, кто решил эту задачу — проведите разбор. Заранее спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | SecondThread | 148 |
5 | atcoder_official | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
Просьба кому-нибудь, кто решил эту задачу — проведите разбор. Заранее спасибо.
Название |
---|
http://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 тебе в помощь по префикс функции, возведению матрицы в степень, и пр.
Спасибо, более менее понятно, попробую на днях реализовать)