Просьба кому-нибудь, кто решил эту задачу — проведите разбор. Заранее спасибо.
→ Обратите внимание
До соревнования
Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.04.2026 04:10:09 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
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 тебе в помощь по префикс функции, возведению матрицы в степень, и пр.
Спасибо, более менее понятно, попробую на днях реализовать)