Mondriaan’s Dream

求用$1\times 2$或$2\times 1$的骨牌覆盖$m\times n$棋盘的方案数

用一维记录轮廓线下方的格子是否已被覆盖

上一个状态只需要考虑当前格子是否已被填上，若已被填上则不能再填，轮廓线状态1->0，若未填，则有竖着填0->1和横着填00->01两种情况

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;

const int N = 1e5 + 5, MOD = 998244353;
const double eps = 1e-8;

int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(int a, int b) { return 1ll * a * b % MOD; }
int bin(int x, int p) {
    int res = 1;
    for (int b = x; p; p >>= 1, b = mul(b, b))
        if (p & 1) res = mul(res, b);
    return res;
}

int h, w;

ll f[2][4000];

ll calc(int h, int w) {
    ll res = 0;
    int cur = 0;
    mem(f[cur ^ 1], 0);
    f[cur ^ 1][0] = 1;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            mem(f[cur], 0);
            for (int k = 0; k <= (1 << w) - 1; k++) {  
                if (!f[cur ^ 1][k]) continue;
                if ((k >> (j - 1)) & 1) f[cur][k ^ (1 << (j - 1))] += f[cur ^ 1][k];
                else {
                    if (j <= w - 1 && ((k >> (j - 1)) & 3) == 0) f[cur][k ^ (1 << j)] += f[cur ^ 1][k];
                    f[cur][k ^ (1 << (j - 1))] += f[cur ^ 1][k];
                }
            }
            cur ^= 1;
        }
    }
    return f[cur ^ 1][0];
}

int main() {
    while(scanf("%d %d", &h, &w), (h != 0 || w != 0)) {
        printf("%lld\n", calc(h, w));
    }
    return 0;
}

Eat the Trees

用若干回路覆盖n*m的棋盘，某些格子已被覆盖。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 12, M = (1 << 12) + 5, MOD = 998244353;

ll f[2][M], tf[M];

int a[N][N];

int mask;

int main() {
    int T, CNT = 0; scanf("%d", &T);
    while(T--) {
        int n, m; scanf("%d %d", &n, &m);
        mask = (1 << (m + 1)) - 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        memset(f, 0, sizeof(f));
        int cur = 0;
        f[cur ^ 1][0] = 1; 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                memset(f[cur], 0, sizeof(f[cur]));
                for (int k = 0; k <= (1 << (m + 1)) - 1; k++) {
                    if (!f[cur ^ 1][k]) continue;
                    int tmp = (k >> (j - 1)) & 3;
                    if (a[i][j] == 1) {
                        if (tmp == 0) f[cur][k ^ (3 << (j - 1))] += f[cur ^ 1][k];
                        if (tmp == 1) {
                            f[cur][k] += f[cur ^ 1][k];
                            f[cur][k ^ (3 << (j - 1))] += f[cur ^ 1][k];
                        }
                        if (tmp == 2) {
                            f[cur][k] += f[cur ^ 1][k];
                            f[cur][k ^ (3 << (j - 1))] += f[cur ^ 1][k];
                        }
                        if (tmp == 3) {
                            f[cur][k ^ (3 << (j - 1))] += f[cur ^ 1][k];
                        }
                    } else {
                        if (tmp == 0) f[cur][k] += f[cur ^ 1][k];
                    }
                }
                if (j == m) {
                    memset(tf, 0, sizeof(tf));
                    for (int k = 0; k <= (1 << m) - 1; k++) {
                        tf[(k << 1) & mask] += f[cur][k];
                    }
                    for (int k = 0; k <= (1 << (m + 1)) - 1; k++) {
                        f[cur][k] = tf[k];
                    }
                }
                cur ^= 1;
            }
        }
        printf("Case %d: There are %lld ways to eat the trees.\n", ++CNT, f[cur ^ 1][0]);
    }
    return 0;
}