Codeforces Round 919 (Div. 2) |
---|
Закончено |
Патрик называет подстроку$$$^\dagger$$$ бинарной строки$$$^\ddagger$$$ хорошей, если эта подстрока содержит ровно одну 1.
Помогите Патрику посчитать количество бинарных строк $$$s$$$, таких что $$$s$$$ содержит ровно $$$n$$$ хороших подстрок и не имеет хороших подстрок длины строго больше $$$k$$$. Обратите внимание, что подстроки различаются по их расположению в строке, например, если $$$s =$$$ 1010, вы должны посчитать оба вхождения 10.
$$$^\dagger$$$ Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
$$$^\ddagger$$$ Бинарная строка — это строка, которая содержит только символы 0 и 1.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — количество требуемых хороших подстрок и максимальная допустимая длина хорошей подстроки.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2500$$$.
Для каждого набора входных данных выведите одно целое число — количество бинарных строк $$$s$$$, таких что $$$s$$$ содержит ровно $$$n$$$ хороших подстрок и не имеет хороших подстрок длины строго больше $$$k$$$. Поскольку это число может быть слишком большим, выведите его по модулю $$$998\,244\,353$$$.
61 13 24 25 46 22450 2391
1 3 5 12 9 259280854
В первом наборе входных данных единственной подходящей бинарной строкой является 1. Строка 01 не подходит, потому что она содержит подстроку 01 длины $$$2 > 1$$$.
Во втором наборе входных данных подходящими бинарными строками являются 011, 110 и 111.
В третьем наборе входных данных подходящими бинарными строками являются 101, 0110, 0111, 1110, 1111.
Название |
---|