传送门
f[i][j][k]f[i][j][k]f[i][j][k]表示前iii个点连了jjj条边,第i−K+1i-K+1i−K+1~iii个点连边数的奇偶性为kkk时的方案数。
转移规定只能从后向前连边。
然后讨论奇偶性转移就行了。
注意从f[i−1]f[i-1]f[i−1]转移过来的时候不用考虑最前面一位。
然后再用f[i][j]f[i][j]f[i][j]转移f[i][j+1]f[i][j+1]f[i][j+1]就行了。
代码:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7;
int n,m,K,f[35][35][(1<<9)+5];
int main(){
n=read(),m=read(),K=read();
int up=1<<(K+1);
f[1][0][0]=1;
for(int i=2;i<=n;++i){
for(int k=0;k<up;++k)if(!(k&1))for(int j=0;j<=m;++j)if(f[i-1][j][k])(f[i][j][k>>1]+=f[i-1][j][k])%=mod;
for(int l=1;l<=K;++l)if(i>l)for(int j=0;j<m;++j)for(int k=0;k<up;++k)
if(f[i][j][k])(f[i][j+1][k^(1<<K)^(1<<(K-l))]+=f[i][j][k])%=mod;
}
cout<<f[n][m][0];
return 0;
}