VK Cup 2022 - Финальный раунд (Engine) |
---|
Закончено |
У Вики есть набор из последовательных положительных целых чисел от $$$1$$$ до $$$2n$$$ включительно.
Ровно $$$k$$$ раз Вика выберет и сделает одно из следующих двух действий:
Напомним, что медианными называются числа, находящиеся ровно в середине множества, если выписать его элементы в возрастающем порядке. Обратите внимание, что набор чисел у Вики всегда имеет чётный размер, поэтому пара медианных чисел определена однозначно. Например, двумя медианными числами набора $$$\{1, 5, 6, 10, 15, 16, 18, 23\}$$$ являются $$$10$$$ и $$$15$$$.
Сколько разных наборов может получить Вика в конце, после $$$k$$$ действий? Выведите это число по модулю $$$998\,244\,353$$$. Два набора считаются разными, если некоторое число входит в один набор и не входит в другой.
В единственной строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^6$$$).
Выведите одно целое число — сколько разных наборов может получить Вика в конце, по модулю $$$998\,244\,353$$$.
3 1
2
3 2
3
3 3
1
7 4
11
23 8
88
100 77
825430474
В первом примере исходный набор Вики — $$$\{1, 2, 3, 4, 5, 6\}$$$, она может удалить из него минимумы и получить $$$\{3, 4, 5, 6\}$$$, а может удалить медианы и получить $$$\{1, 2, 5, 6\}$$$.
Во втором примере Вика может получить либо $$$\{1, 6\}$$$, либо $$$\{3, 6\}$$$, либо $$$\{5, 6\}$$$. Например, набор $$$\{3, 6\}$$$ Вика может получить, если первым действием удалит минимумы ($$$\{1, 2, 3, 4, 5, 6\} \rightarrow \{3, 4, 5, 6\}$$$), а вторым действием удалит медианы ($$$\{3, 4, 5, 6\} \rightarrow \{3, 6\}$$$).
В третьем примере вне зависимости от того, какие операции будет делать Вика, в итоге получится пустой набор.
Название |
---|