Untitled
unknown
c_cpp
a month ago
1.1 kB
0
Indexable
Never
#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; }