#P52069. 「THUPC 2021 初赛」合法序列

「THUPC 2021 初赛」合法序列

题目描述

对于一个长度为 nn0-1\text{0-1} 序列 ss,我们将它的位从左到右、从零开始编号,记为 s0,s1,,sn1s_0, s_1, \ldots , s_{n-1}

给定一个正整数 kk,从 ss 中取出某个长度为 kk 的子段。将这个子段解释为一个左侧为高位、右侧为低位的 kk 位二进制数,记为 tt,则有 0t<2k0 \le t < 2^k

ssnk+1n - k + 1 个长度为 kk 的子段,如果对于其中的每一个子段,如上解释为二进制数 tt 后,ss 的编号为 tt 的位(即 sts_t)都是 11,则说 ss 是合法的。保证 2kn2^k \le n,即 tt 作为 ss 的下标不会越界。

给定 n,kn, k,求合法的 ss 的数量。由于方案数可能较大,只需给出方案数模 998,244,353998,244,353 的结果作为答案。

输入格式

输入有一行,包含两个用空格隔开的正整数 n,kn, k

保证 1k41 \le k \le 42kn5002^k \le n \le 500

输出格式

输出一行,包含一个非负整数,即合法方案数模 998,244,353998,244,353 的结果。

样例

4 2

2

有两个满足要求的序列:0,1,1,10, 1, 1, 11,1,1,11, 1, 1, 1

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。