[题解] P10975 Mondriaan's Dream / 蒙德里安的梦想

xingchen666 · 2026-05-06 03:20:30 · 题解

状态压缩 dp 模板题，但是题解区没看到 O(n3^n) 的做法，所以自己记录一下。努力去尽量清晰直白地写了。

对于每一行的状态的枚举，我们把第 j 列的格子的值用 0,1,2 三个数字的其中一个表示。这里定义：

• 0 表示该格子是横放矩形的一格
• 1 表示该格子是竖向矩形的上面一格
• 2 表示该格子是竖向矩形的下面一格

这时候每行的状态可以由一个 m 位三进制数描述了。接下来考虑如何转移状态。

可以发现，如果一个格子值为 2 ，那么它上面的格子就必须为 1；反之，上面的格子一定不能为 1。对当前行的状态，找到上一行所有满足该条件的状态的值全部加起来就行了。

这里不需要枚举，我们可以提前计算并存起来。定义 sum_{i,stt} 为第 i 行里，状态满足 stt 所描述条件的那些状态的值之和。这里 stt 是一个二进制数，第 j 位表示第 j 列的格子是否应为 1。

可以使用滚动数组省去一点点空间。时间复杂度 O(n3^n)

::::success[Code]

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

ll read() {
    ll res = 0, neg = 1; char ch = getchar();
    while(ch<'0' or ch>'9') { if(ch == '-') neg = -1; ch = getchar(); }
    while(ch>='0' and ch<='9') res = res*10 + ch-'0', ch = getchar();
    return res * neg;
}

void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x < 10) putchar(x+'0');
    else write(x/10), putchar(x%10+'0');
}

const int N = 20;

int n,m;

int a[N];
ll sum[2][2500];

int main() {
    while(true) {
        n = read(), m = read();
        if(!n and !m) break ;
        if(m > n) swap(n,m); 

        int sttcnt = 1;
        for(int i=1; i<=m; i++) sttcnt *= 3;

        ll ans = 0;

        for(int i=1, op=0; i<=n; i++, op^=1) {
            for(int stt2=0; stt2<(1<<m); stt2++) {
                sum[op^1][stt2] = 0;
                if(i == 1) sum[op][stt2] = 0;
            }
            if(i == 1) sum[op][0] = 1;

            for(int stt=0; stt<sttcnt; stt++) {
                int stt2 = 0, stt3 = 0;
                bool is_inlaw = true; int cnt0 = 0;

                for(int j=1, tmp=stt; j<=m; j++, tmp/=3) {
                    a[j] = tmp%3;

                    if(a[j] == 0) cnt0++;
                    else {
                        if(cnt0&1) {
                            is_inlaw = false;
                            break;
                        }
                        cnt0 = 0;
                    }

                    if(a[j] == 2) stt2 |= (1<<(j-1));
                    if(a[j] == 1) stt3 |= (1<<(j-1));
                }
                if(cnt0&1) is_inlaw = false;

                if(!is_inlaw) continue ;

                ll res = sum[op][stt2];
                sum[op^1][stt3] += res;

                if(i == n and stt3 == 0) ans += res;
            }
        }

        write(ans), putchar('\n');
    }

    return 0;
}

::::