C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 19320K, 提交时间: 2020-10-08 17:49:22

#include<cstdio>
#include<iostream>
const int p=1e9+7;
using namespace std;
 
int n,m,k;
const int N=40,S=522;
int f[N][N][S][10];
 
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	
	f[2][0][0][0]=1;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int s=0;s<(1<<(k+1));s++)
			{
				for(int l=0;l<k;l++)
				{
					f[i][j][s][l+1]+=f[i][j][s][l];
					f[i][j][s][l+1]%=p;
					if(i-k+l>0&&j<m)
						f[i][j+1][s^(1<<k)^(1<<l)][l]+=f[i][j][s][l],
						f[i][j+1][s^(1<<k)^(1<<l)][l]%=p;
				}
				if(!(s&1))
					f[i+1][j][s>>1][0]+=f[i][j][s][k],
					f[i+1][j][s>>1][0]%=p;
			}
		
	printf("%d\n",f[n+1][m][0][0]);//不用算sum了
	return 0;
}
 

C++ 解法, 执行用时: 40ms, 内存消耗: 22392K, 提交时间: 2022-07-24 20:54:24

#include <bits/stdc++.h>
const int MOD = 1e9+7;
using namespace std;
 
int n, m, k;
int f[44][44][555][11];
 
signed main() {
    cin >> n >> m >> k;
	f[2][0][0][0]=1;
	for (int i=2;i<=n;i++)
		for (int j=0;j<=m;j++)
			for (int s=0;s<(1<<(k+1));s++) {
				for (int l=0;l<k;l++){
					f[i][j][s][l+1]+=f[i][j][s][l];
					f[i][j][s][l+1]%=MOD;
					if(i-k+l>0&&j<m)
						f[i][j+1][s^(1<<k)^(1<<l)][l]+=f[i][j][s][l],
						f[i][j+1][s^(1<<k)^(1<<l)][l]%=MOD;
				}
				if(!(s&1)) {
					f[i+1][j][s>>1][0]+=f[i][j][s][k];
					f[i+1][j][s>>1][0]%=MOD;
                }
			}
	cout << f[n + 1][m][0][0] << endl;
	return 0;
}