Эта версия задачи отличается от следующей только ограничением на $$$n$$$.
Обратите внимание, что ограничение по памяти в этой задаче ниже, чем в других.
У вас есть вертикальная полоска из $$$n$$$ ячеек, последовательно пронумерованных сверху вниз от $$$1$$$ до $$$n$$$.
У вас также есть токен, изначально расположенный в ячейке $$$n$$$. Вы будете двигать токен вверх до тех пор, пока он не окажется в ячейке $$$1$$$.
Пусть в некоторый момент токен находится в ячейке $$$x > 1$$$. Один сдвиг токена может иметь любой из следующих двух видов:
Найдите число способов, которыми токен может добраться из ячейки $$$n$$$ в ячейку $$$1$$$ за один или более сдвигов, и выведите это число по модулю $$$m$$$. Обратите внимание, что если есть несколько способов переместить токен из одной ячейки в другую за один сдвиг, все эти способы считаются различными (смотрите пояснение к примерам для лучшего понимания).
Единственная строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$10^8 < m < 10^9$$$; $$$m$$$ — простое число) — длину полоски и число, по модулю которого необходимо вычислить ответ.
Выведите число способов для токена добраться из ячейки $$$n$$$ в ячейку $$$1$$$, по модулю $$$m$$$.
3 998244353
5
5 998244353
25
42 998244353
793019428
В первом тесте есть три способа добраться из ячейки $$$3$$$ в ячейку $$$1$$$ за один сдвиг: с помощью вычитания $$$y = 2$$$, а также с помощью деления на $$$z = 2$$$ или $$$z = 3$$$.
Также есть два способа добраться из ячейки $$$3$$$ в ячейку $$$1$$$ через ячейку $$$2$$$: сначала вычесть $$$y = 1$$$, а потом либо снова вычесть $$$y = 1$$$, либо поделить на $$$z = 2$$$.
Таким образом, всего способов пять.
Название |
---|