Shared code

#include <bits/stdc++.h>
using namespace std;

int n, m, dp[1010][21][2050] = {0};
const int M = 1e9+7;

void add(int & x, int y) {
    x += y;
    if (x >= M) x -= M;
}

int main () {
    cin >> n >> m;
    if (n < m) swap(n, m);
    int maskmx = (1 << m) * 2; 

    dp[0][m][0] = 1; //初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j == 0) { //換個橫行了
                for (int mask = 0; mask < (1 << m); mask++) dp[i][j][mask << 1] = dp[i-1][m][mask];
                continue;
            }
            for (int mask = 0; mask < maskmx; mask++) {
                if (__builtin_popcount(mask)%2 != ( (i - 1) * m + j - 1) % 2) continue; //判奇偶，把假解丟掉
                bool left = mask & (1 << (j - 1)),   up = mask & (1 << j);
                if (left or up) { //放不了
                    int newmask = mask -  (mask & (1 << (j - 1)))  -  (mask & (1 << j));
                    add(dp[i][j][newmask], dp[i][j - 1][mask]);
                }
                else { //放的了
                    int newmask = mask + (1 << (j - 1));
                    if (i != n) add(dp[i][j][newmask], dp[i][j - 1][mask]);
                    newmask = mask + (1 << j);
                    if (j != m)add(dp[i][j][newmask], dp[i][j - 1][mask]);
                }
            }
        }
    }

    cout << dp[n][m][0] << '\n';
return 0;}