按照一般得思路，我们应该记录那些元素被选择了。可是 $n$ 太大了，考虑转化一下。

$m$ 很小只有 $4$，这启发我们从 $1$ 开始到 $n$ 一个一个考虑，思考一下填入需要满足什么要求：

具体的，我们考虑在一个序列中插入一些数，使这个序列一直满足题目的要求。

首先第 $1,2$ 个要求是肯定满足得，因为我们就是在枚举要填入什么元素，所以肯定不会出现填入的数大于 $n$ 或者有重复的情况。

因为插入的顺序是递增的，所以一定有 $a_i<a_{i-1}$，也就一定满足 $a_i\le a_{i+1}+m$。

所以新填入的数与后面的关系一定是满足题目要求的，只需要考虑与前面的关系就行了。

注意这里有一个细节就是第 $1$ 个位置可以随便填，因为它根本就没有前面的元素。

考虑会影响填入 $x$ 的有什么，显然 $x$ 只有插入到 $[x-m,x)$ 这些数后面才行，那么暴力的考虑，直接状压记录这 $m$ 个位置都填的什么。

在考虑了上面之后，状态就很好想出来了。

设 $f_{i,j,S}$ 表示现在考虑到了填 $i$，已经填了 $j$ 个数，$[x-i,i)$ 这个区间内都用了 $S$ 的数，那么有转移方程：

$f_{i+1,j+1,(2S+1)\bmod(2^m)}\gets f_{i,j,S}\times (\operatorname{popcount}(S)+1)$

$f_{i+1,j,(2S)\bmod (2^m)}\gets f_{i,j,S}$

这样的时间复杂度为 $O(n\times k\times 2^m)$ 的。