Untitled

 avatar
unknown
c_cpp
a year ago
1.1 kB
1
Indexable
#include<iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 2002;
const ll MOD = 1e9 + 7;
int n, m;
ll dp[maxn][maxn];

void rec(int i, int j, int bitmask, int next_mask) {
    if(j >= m) {
        return;
    }
    if(i >= n) {
        dp[j + 1][next_mask] += (dp[j][bitmask] % MOD);
        dp[j][bitmask] %= MOD;
    }
    else {
        int take_row = (1 << i);
        if(bitmask & (1 << i)) {
            rec(i + 1, j, bitmask, next_mask);
        }
        else {
            rec(i + 1, j, bitmask, next_mask | (1 << i));
            int try_to_take = (take_row << 1);
            if(i + 1 < n && !(bitmask & try_to_take)) {
                rec(i + 2, j, bitmask, next_mask);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    
    for(int j = 0; j < m; j++) {
        for(int bitmask = 0; bitmask < (1 << n); bitmask++) {
            rec(0, j, bitmask, 0);
        }
    }
    cout << dp[m][0] % MOD << endl;;
    return 0;
}