传送门
显然可以发现把(k)状压
显然可以发现三维的dp，(f[i][j][k])代表当前到(i)，已经连了(j)条边，当前(i to i-k)奇偶性为(k)，然而会重复算
所以再加一维(t)，表示上一次连的边为(i->i-k+c)
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int mod=1e9+7;
int n,m,k,f[32][32][1<<9][9];
int main()
{
read(n),read(m),read(k);
int tot=1<<(k+1);
f[2][0][0][0]=1;
for(rg int i=2;i<=n;i++)
for(rg int j=0;j<=m;j++)
for(rg int y=0;y<tot;y++)
{
for(rg int t=0;t<k;t++)
{
(f[i][j][y][t+1]+=f[i][j][y][t])%=mod;
if(j<m&&i-k+t>=1)(f[i][j+1][y^(1<<k)^(1<<t)][t]+=f[i][j][y][t])%=mod;
}
if(!(y&1))f[i+1][j][y>>1][0]=f[i][j][y][k];
}
printf("%d
",f[n+1][m][0][0]);
}