题意

一条长为 \(n\) 的数轴，可以从任意整点 \(\in [1, n]\) 出发，假设当前在 \(x\) ，下一步能到达的点 \(y\) 需要满足，\(y\) 从未到过，且 \(1 \le y \le x + m\) ，问长恰好为 \(k\) 的合法路径条数。

数据范围

对于 \(F1\) 有 \(1 \le n \le 10^5, 1 \le k \le \min(n, 12), 1 \le m \le 4\)

对于 \(F2​\) 有 \(1 \le n \le 10^9​\) 。

题解

比较 \(\text{tricky}\) 的一个题。

考虑我们当前假设经过的路径为 \(v_1, v_2, \cdots, v_p\) ，我们当前可以添加一个 \(x < \min_{i = 1}^{p} \{v_i\}\) 。显然我们是一定可以添加到队尾的，其次我们可以添加到那些 \(v_i \le x + m\) 的前面。

那么我们就得到一个很显然的 \(dp\) 了，考虑从大到小依次考虑每个数填还是不填就能轻松转移了。

具体来说设 \(dp[i][j][sta]\) 为当前在第 \(i\) 个位置，路径长度为 \(j\) ，最后 \(m\) 个位置状压后的状态为 \(sta\) 。

每次转移的时候，如果不填直接转过去，填的话可以转到后 \(m\) 个有 \(1\) 的状态以及队尾，也就是 \(1 + bitcount(sta)\) 。

这样 \(dp\) 刚好每条路都能一一对应上。

对于 \(F1\) 直接 \(\mathcal O(nk2^m)\) 就行了，\(F2\) 考虑利用矩阵快速幂优化到 \(\mathcal O((k2^m)^3 \log n)\) 。（说实话 \(F2\) 没啥意思。。）

代码

#include 
    
     #define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)#define Set(a, v) memset(a, v, sizeof(a))#define Cpy(a, b) memcpy(a, b, sizeof(a))#define debug(x) cout << #x << ": " << (x) << endlusing namespace std;template
     
       inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }template
      
        inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }inline int read() {    int x(0), sgn(1); char ch(getchar());    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);    return x * sgn;}void File() {#ifdef zjp_shadow    freopen ("F1.in", "r", stdin);    freopen ("F1.out", "w", stdout);#endif}const int N = 1e5 + 1e3, K = 14, M = 4, Mod = 1e9 + 7;int dp[N][K][1 << M];int main() {    File();    int n = read(), k = read(), m = read();    dp[0][0][0] = 1;    Rep (i, n) For (j, 0, k) Rep (sta, 1 << m) {        (dp[i + 1][j][sta >> 1] += dp[i][j][sta])%= Mod;        int res = dp[i][j][sta] * (1ll + __builtin_popcount(sta)) % Mod;        (dp[i + 1][j + 1][(sta >> 1) | (1 << m - 1)] += res) %= Mod;    }    int ans = 0;    Rep (sta, 1 << m)        (ans += dp[n][k][sta]) %= Mod;    printf ("%d\n", ans);    return 0;}