| Algo Cup 2025 by csspace.io (Финал) |
|---|
| Закончено |
Напомним, что бинарная строка — это строка, состоящая из символов 0 и/или 1. Подстрокой бинарной строки назовем её непрерывную подпоследовательность.
Предположим, у вас есть бинарная строка $$$s$$$. Вы можете проводить с ней следующую последовательность операций:
После каждого удаления получившиеся части строки склеиваются в том же порядке. Операции можно завершить в любой момент (в том числе можно оставить строку без изменений).
Назовем бинарную строку красивой, если из неё такой последовательностью операций можно удалить все нули. Например:
Ваша задача — посчитать количество красивых бинарных строк длины $$$n$$$.
В единственной строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2\,000\,000$$$).
Выведите одно целое число — количество красивых бинарных строк длины $$$n$$$, взятое по модулю $$$998244353$$$.
2
4
3
7
4
13
13
724
42
1346030
1234567
163685965
Для $$$n=2$$$ все бинарные строки красивые.
Для $$$n=3$$$ все бинарные строки, кроме 010, являются красивыми.
| Название |
|---|


