CF1920E Counting Binary Strings

Patrick 认为一个二进制字符串的子串是“好”的，当且仅当该子串恰好包含一个 $1$。 请帮助 Patrick 计算有多少个二进制字符串 $s$ 满足以下条件： - $s$ 恰好包含 $n$ 个“好”子串； - $s$ 没有长度严格大于 $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$ 的数量。由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，唯一合适的二进制字符串是 $1$。字符串 $01$ 不合适，因为它包含了一个长度为 $2 > 1$ 的“好”子串 $01$。 在第二个测试用例中，合适的二进制字符串有 $011$、$110$ 和 $111$。 在第三个测试用例中，合适的二进制字符串有 $101$、$0110$、$0111$、$1110$ 和 $1111$。 由 ChatGPT 4.1 翻译