题目描述
见原题面
算法1
(DFS)
时间复杂度
$O(?)$
不过应该大到没边
算法2
(状压DP)
其他题解已解释清楚,不再赘述,注意信息见下方代码注释。
时间复杂度
$O(mk2^{3n})$(?),不过由于排除了大量非法状态,所以实际运行起来是比较快的。
C++ 代码
/*
似乎是普通的状压DP
然而本题列数可远大于行数,故可以选择列而不是行。
由于要考虑前两列,还限制马的个数,故要开四维数组,写起来就比较难受,一开始竟然忘记取模了...
注意条件不能只有(now&(prev>>2))==0,(now&(pre_prev>>1))==0和(prev&(pre_prev>>1))==0,还要倒过来,
否则像(前一行)=00100,(当前行)=10000这样的状态会误判为合法。
*/
#include <cstdio>
#include <algorithm>
#define MOD 1000000007
const int MAXM=101,MAXN=6,MAXS=1+(1<<MAXN),MAXK=21;
typedef unsigned int usi;
using namespace std;
usi dp[MAXM][MAXS][MAXS][MAXK];
inline int popcnt(usi x) {
int cnt=0;
while(x>0) {
cnt++;
x&=(x-1);
}
return cnt;
}
int main(){
dp[0][0][0][0]=1;
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
n=1<<n;
for(int i=1; i<=m; i++) {
for(int a=0; a<n; a++) {
for(int b=0; b<n; b++) {
if((a&(b>>2))||(b&(a>>2))) continue;
for(int c=0; c<n; c++) {
if((b&(c>>2))||(c&(b>>2))) continue;
if((a&(c>>1))||(c&(a>>1))) continue;
int pop=popcnt(a);
for(int t=pop; t<=k; t++) {
dp[i][a][b][t]=(dp[i][a][b][t]+dp[i-1][b][c][t-pop])%MOD;
}
}
}
}
}
usi res=0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
res=(res+dp[m][i][j][k])%MOD;
}
}
printf("%d",res);
return 0;
}