trick：从值域考虑。
好题。但是感觉和 CF1151F 差不多难。两题都是 *3000 但是一紫一黑。
题意：
对长度为 \(k\)，值域 \(n\) 的序列计数：
\(a_i \leq a_{i-1}+m\)
\(\forall i,j,a_i \neq a_j\)
\(k \leq 10^9,n \leq 12, m \leq 4\)，easy ver \(k \leq 10^5\)。
\(n\) 显然是供状压的东西。发现难弄的限制都在值域上，因此从值域考虑。
考虑从小到大确认每个数是否填入，以插入的形式计数。显然需要记录已经填入数的个数。为了知道一个数能插入到几个数后，需要知道 \(i-m\) 到 \(i-1\) 中有几个数。发现后两者均很好转移，于是 easy ver 做完了，复杂度 \(O(nk2^m)\)。
\[dp_{i+1, 2S \land (2^m-1), j} \gets dp_{i,S,j} \ (j \leq k)\\ dp_{i+1, 2S+1 \land (2^m-1), j+1} \gets dp_{i, S, j} \cdot (\text{popcount}(S) + 1) \ (j < k) \]发现转移与 \(i\) 无关，写成矩乘即可 \(O((2^mk)^3 \log n)\)。
有一点细节是强制完成状态为 \(j=k,S=0\)，矩乘时特判转移到这里的。这样子完成状态仅有一个，不用额外枚举，代码中的转移也会清晰不少。这是魏老师题解中的做法，仔细看了看其它题解都没有这样的设置。需要允许 \(dp_{i,k,0}\) 推到 \(dp_{i+1,k,0}\)，这样相当于取了末尾为所有数字的答案。orz 魏老师。
#include <cstdio>
#include <cstring>
using namespace std;
int lim;
const int mod = 1e9 + 7;
struct matrix {
int a[205][205];
matrix() {memset(a, 0, sizeof(a));}
int* operator [] (int i) {
return a[i];
}
matrix operator * (const matrix &tmp) {
matrix t;
for(int i = 0; i <= lim; i++)
for(int j = 0; j <= lim; j++)
for(int k = 0; k <= lim; k++)
t[i][j] = (t[i][j] + 1ll * a[i][k] * tmp.a[k][j] % mod) % mod;
return t;
}
matrix operator ^ (int tmp) const {
matrix ans, t = *this;
for(int i = 0; i <= lim; i++) ans[i][i] = 1;
for(; tmp; tmp >>= 1) {
if(tmp & 1) ans = ans * t;
t = t * t;
}
return ans;
}
void print(int n) {
for(int i = 0; i <= lim; i++) {
for(int j = 0; j <= lim; j++) printf("%d ", a[i][j]);
printf("\n");
}
}
} ;
int main() {
int n, k, m; scanf("%d %d %d", &n, &k, &m);
lim = k << m;
int all = (1 << m) - 1;
matrix t;
for(int S = 0; S < (1 << m); S++) {
for(int j = 0; j < k; j++) {
int num = __builtin_popcount(S), s = (S << 1) & all;
t[(j << m) + S][(j << m) + s] = 1;
if(j == k-1) t[(j << m) + S][k << m] = num + 1;
else t[(j << m) + S][(j+1 << m) + s + 1] = num + 1;
}
}
t[k << m][k << m] = 1;
t = t ^ n; matrix a; a[0][0] = 1; // 用行向量
a = a * t; printf("%d\n", a[0][k << m]);
}
AC 完后发现了二维矩乘做法，感觉很厉害，转移也很方便。
struct mat
{
int n,m,v[13][20][13][20];
mat(){}
mat(int N,int M,int one=0)
{
n=N;m=M;memset(v,0,sizeof(v));
if(one) for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) v[i][j][i][j]=1;
}
}base;
const int mod=1e9+7;
inline mat operator*(const mat &a,const mat &b)
{
mat c=mat(a.n,a.m);
for(int i=0;i<=a.n;i++)
for(int j=0;j<=a.m;j++)
for(int k=0;k<=a.n;k++)
for(int l=0;l<=a.m;l++)
for(int x=0;x<=a.n;x++)
for(int y=0;y<=a.m;y++)
(c.v[i][j][x][y]+=a.v[i][j][k][l]*b.v[k][l][x][y])%=mod;
return c;
}
inline mat jjksm(mat di,int mi)
{
mat ret=mat(di.n,di.m,1);
while(mi) {if(mi&1) ret=ret*di;mi>>=1;di=di*di;}
return ret;
}
int n,m,k;
#define all ((1<<m)-1)
signed main()
{
n=read();k=read();m=read();
base=mat(k,all);
for(int i=0;i<=k;i++) for(int sta=0;sta<(1<<m);sta++) base.v[i][sta][i][(sta<<1)&all]=1;
for(int i=0;i<k;i++)
for(int sta=0;sta<(1<<m);sta++)
{
base.v[i][sta][i+1][((sta<<1)|1)&all]=__builtin_popcount(sta)+1;
}
mat ret=jjksm(base,n);
int ans=0;
for(int sta=0;sta<(1<<m);sta++) (ans+=ret.v[0][0][k][sta])%=mod;
write(ans);
pc('\n');
}