[THUPC2021 初赛] 合法序列
题目描述
对于一个长度为 $n$ 的 $\text{0-1}$ 序列 $s$,我们将它的位从左到右、从零开始编号,记为 $s_0, s_1, \ldots , s_{n-1}$。
给定一个正整数 $k$,从 $s$ 中取出某个长度为 $k$ 的子段。将这个子段解释为一个左侧为高位、右侧为低位的 $k$ 位二进制数,记为 $t$,则有 $0 \le t < 2^k$。
$s$ 有 $n - k + 1$ 个长度为 $k$ 的子段,如果对于其中的每一个子段,如上解释为二进制数 $t$ 后,$s$ 的编号为 $t$ 的位(即 $s_t$)都是 $1$,则说 $s$ 是合法的。保证 $2^k \le n$,即 $t$ 作为 $s$ 的下标不会越界。
给定 $n, k$,求合法的 $s$ 的数量。由于方案数可能较大,只需给出方案数模 $998, 244, 353$ 的结果作为答案。
输入输出格式
输入格式
输入有一行,包含两个用空格隔开的正整数 $n, k$。
保证 $1 \le k \le 4$,$2^k \le n \le 500$。
输出格式
输出一行,包含一个非负整数,即合法方案数模 $998, 244, 353$ 的结果。
输入输出样例
输入样例 #1
4 2
输出样例 #1
2
说明
**【样例解释 #1】**
有两个满足要求的序列:$0, 1, 1, 1$ 和 $1, 1, 1, 1$。
**【题目来源】**
来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。
题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。