Counting Binary Strings
Contest: Codeforces Round 919 (Div. 2)
Difficulty rating: 2100
Tags: combinatorics, dp, math

Patrick calls a substring$$$^\dagger$$$ of a binary string$$$^\ddagger$$$ good if this substring contains exactly one 1.

Help Patrick count the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Note that substrings are differentiated by their location in the string, so if $$$s =$$$ 1010 you should count both occurrences of 10.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$^\ddagger$$$ A binary string is a string that only contains the characters 0 and 1.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2500$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — the number of required good substrings and the maximum allowed length of a good substring.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2500$$$.

Output format:
For each test case, output a single integer — the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Since this integer can be too large, output it modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the only suitable binary string is 1. String 01 is not suitable because it contains a substring 01 with length $$$2 > 1$$$.

In the second test case, suitable binary strings are 011, 110 and 111.

In the third test case, suitable binary strings are 101, 0110, 0111, 1110, and 1111.

Example input:
6
1 1
3 2
4 2
5 4
6 2
2450 2391

Example output:
1
3
5
12
9
259280854

Editorial:
Let's first solve the problem where we are given some string $$$s$$$ and must count the number of good substrings. To do this, we use the technique of counting contributions. For every $$$1$$$ in $$$s$$$, we find the number of good substrings containing that $$$1$$$. Consider the following example:
$$$$$$ \underbrace{00001}_{a_1} \! \! \! \, \underbrace{ \; \, \! 0001}_{a_2} \! \! \! \, \underbrace{ \; \, \! 00000001}_{a_3} \! \! \! \, \underbrace{ \; \, \! 0001}_{a_4} \! \! \! \, \underbrace{ \; \, \! 000}_{a_5} $$$$$$
The number of good substrings in this example is $$$a_1 a_2 + a_2 a_3 + a_3 a_4 + a_4 a_5$$$. We can create such an array for any string $$$s$$$, and the number of good substrings of $$$s$$$ is the sum of the products of adjacent elements of the array.
This motivates us to reformulate the problem. Instead, we count the number of arrays $$$a_1,a_2,...,a_m$$$ such that every element is positive and the sum of the products of adjacent elements is exactly equal to $$$n$$$. Furthermore, every pair of adjacent elements should have sum minus $$$1$$$ be less than or equal to $$$k$$$. We can solve this with dynamic programming.
$$$$$$ dp_{i,j} = \text{number of arrays with sum $i$ and last element $j$} $$$$$$
$$$$$$ dp_{i, j} = \sum_{p=1}^{\min({\lfloor \frac{i}{j} \rfloor},\, k-j+1)}{dp_{i - j \cdot p,p}} $$$$$$
The key observation is that we only have to iterate $$$p$$$ up to $$$\lfloor \frac{i}{j} \rfloor$$$ (since if $$$p$$$ is any greater, $$$j \cdot p$$$ will exceed $$$i$$$). At $$$j=1$$$, we will iterate over at most $$$\lfloor \frac{i}{1} \rfloor$$$ values of $$$p$$$. At $$$j=2$$$, we will iterate over at most $$$\lfloor \frac{i}{2} \rfloor$$$ values of $$$p$$$. In total, at each $$$i$$$, we will iterate over at most $$$\lfloor \frac{i}{1} \rfloor + \lfloor \frac{i}{2} \rfloor +\cdots + \lfloor \frac{i}{i} \rfloor \approx i \log i$$$ values of $$$p$$$. Thus, the time complexity of our solution is $$$O(n^2\log n)$$$.