绷不住了，洛谷上的 dp 没一个表述清楚了，一怒之下写一篇题解。注意本题解只讲 dp 部分。
首先转化不合法的充要条件就是：设相邻两个棋子中间间隔数量为 \(b\)，那么对于任意非负整数 \(i\) 都有 \((d+1)|\sum (b\& 2^i)\)。其中 \(\&\) 是按位与运算。所以我们要计数一个有序的并且包含 \(\dfrac{k}{2}\) 个元素的 \(b\) 数组。
那么我们考虑 \(f_{i,j}\) 表示这 \(\dfrac{k}{2}\) 个数每个都填了二进制上前 \(i\) 位并且这 \(i\) 位满足是 \(d+1\) 倍数的条件，并且选出数字总和为 \(j\) 的方案数。那么这时我们就可以枚举第 \(i+1\) 位的填数字情况，很显然是要填 \(p(d+1)\) 个 \(1\)，其中 \(p\in\mathbf{N}\)。我们就枚举 \(p\)，那么总和增量就是 \(2^i\times p(d+1)\)；我们可以考虑哪些位置选了数，那么产生的贡献就是 \(f_{i,j}\times\left(\begin{matrix}\dfrac{k}{2}\\p(d+1)\end{matrix}\right)\) 这么多，加到 \(f_{i,j+2^i\times p(d+1)}\) 上。
最后我们要通过 \(b\) 数组还原棋子的排布情况，那么我们枚举 \(j\)，由于有 \(j+\dfrac{k}{2}\) 个位置是不能选的（间隔和终点），那么剩余的位置数量是 \(n-j-\dfrac{k}{2}\)，\(j\) 对方案的贡献就是 \(f_{L,j}\times\left(\begin{matrix}n-j-\dfrac{k}{2}\\\dfrac{k}{2}\end{matrix}\right)\) 这么多。其中 \(L\) 是最高位。最后用 \(\left(\begin{matrix}n\\k\end{matrix}\right)\) 减去不合法答案的数量即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=10005,L=25,K=105,mod=1000000007;
int n,k,d,f[L][N],C[N][K];
inline void add(int&x,int y) {
x=(x+y)%mod;
return;
}
int main() {
scanf("%d %d %d",&n,&k,&d);
int lim=__lg(n);
C[0][0]=1;
for (int i=1;i<=n;i++) {
C[i][0]=1;
for (int j=1;j<=k;j++) {
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
f[0][0]=1;
for (int i=0;i<=lim;i++) {
for (int j=0;j<=n;j++) {
for (int x=0;j+(x<<i)*(d+1)<=n&&x*(d+1)<=k/2;x++) {
add(f[i+1][j+(x<<i)*(d+1)],1ll*f[i][j]*C[k/2][x*(d+1)]%mod);
}
}
}
int ans=0;
for (int i=0;i<=n;i++) {
if (n-i-k/2>=0) add(ans,1ll*f[lim+1][i]*C[n-i-k/2][k/2]%mod);
}
ans=(C[n][k]-ans+mod)%mod;
printf("%d",ans);
return 0;
}