已经没办法再简单的状压dp入门练习

题目：
有一个N*M(N<=5,M<=1000)的棋盘，现在有1*2及2*1的小木块无数个，要盖满整个棋盘，有多少种方式？答案只需要mod1,000,000,007即可。

例如：对于一个2*2的棋盘，有两种方法，一种是使用2个1*2的，一种是使用2个2*1的。
分析：此题由于N比较小，所以可以通过状态压缩，去搜索每一个状态，然后根据前一列对后一列的影响，这样我们只要求出第m+1列状态为0的情况的个数，就是正解

accode:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 100;
const int mod = 1e9 + 7;
int T, n, m;
ll dp[1005][(1 << 5) + 5];
void dfs(int i, int j, int state, int nex) {
    if (j == n) {
        dp[i + 1][nex] += dp[i][state];
        //cout << i + 1 << " " << nex << " " << dp[i + 1][nex]<<endl;
        dp[i + 1][nex] = dp[i + 1][nex] % mod;
        return;
    }
    if ((state&(1 << (j))) >0) {
        dfs(i, j + 1, state, nex);
    }
    if ((state&(1 << (j))) == 0) {
        dfs(i, j + 1, state, (nex | (1 << (j))));
    }
    if ((state&(1 << (j))) == 0 && (j + 1<n) && ((state&(1 <<( j + 1))) == 0)) {
        dfs(i, j + 2, state, nex);
    }
}
int main()
{
    memset(dp, 0, sizeof(dp));
    scanf("%d%d", &n, &m);
    dp[1][0] = 1;
    //int t = (3 & (1 << (1)));
    //cout <<t << endl;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <(1 << (n)); j++) {
            dfs(i, 0, j, 0);
        }
    }
    cout << dp[m + 1][0] << endl;
    return 0;
}