题解：P10975 Mondriaan's Dream
longlinyu7
·
·
题解
题目分析
用 1 \times 2 的小矩形填充一个大矩形，可以横着放或者竖着放，问方案数。
解题思路
可以观察到数据范围很小 N,M \le 11，可以考虑阶乘级算法或者指数级算法，那么考虑到要求记录方案数，尝试使用状态压缩。
设计状态
根据状态压缩的套路，把每一行当做一个“状态”。
再考虑每一行中每一列的方格归属情况：
- 可能与上一行的方格属于一个竖着放的小矩形，将这个状态设为 1。
- 剩下的所有情况都把状态设为 0，比如连续两个位置安排一个横着的 1 \times 2 矩形，或者与下一行的方格属于一个竖着的矩形。
为什么这样安排呢？
因为我们是从上到下遍历，枚举到第 i 行的时候，需要考虑上一行对当前行的影响，第一种情况的时候，第 i-1 行对第 i 行的状态产生了影响。第二种情况的时候并没有产生影响。
综上所述，设 f_{i,s} 表示前 i 行，第 i 行的状态为 s 时的方案数。
### 状态转移
$$f_{i,j}= f_{i,j}+f_{i-1,k}$$
转移条件。
- 状态 $j$ 和状态 $k$ 执行**按位与**运算得到的结果是 $0$。
这样就保证了每个数字 $1$ 的下方必须是 $0$，代表着补全竖着的 $1 \times 2$ 的矩形。
- 状态 $j$ 和状态 $k$ 执行**按位或**运算的二进制表示中，每一段连续的 $0$ 必须都是偶数个。
偶数个 $0$ 代表着横着的 $1 \times 2$ 的矩形。奇数个的话就无法满足了。
这两个条件保证了状态转移的合法性，对于条件一，直接计算就好了，对于条件二，可以提前预处理每一个状态是否合法，具体细节见代码。
### 边界处理与输出答案
初始状态，$f_{0,0}=1$。
很明显，答案是 $f_{n,0}$，因为第 $n$ 行的时候，已经到了最后，不能再有 $1$ 状态了。
# AC CODE
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9;
const int N=13;
ll f[N][1<<N]; //! 不开 long long 见祖宗！！！！！
int n,m;
int vis[1<<N]; // 预处理状态是否合法
signed main(){
while(cin>>n>>m){
if(n==0&&m==0)return 0;
memset(f,0,sizeof(f)); // 多测清空
f[0][0]=1; // 初始状态
// 预处理
for(int i=0;i<(1<<m);i++){
//cnt 记录每一段的奇偶性
// has_odd 记录是否有一段是有奇数个0的
bool cnt=0,has_odd=0;
// 一个合法状态中， 连续的0 必须有偶数个
for(int j=0;j<m;j++){
// (i>>j)&1 是判断状态i的第j位是否为1，为1就开始新的一段
if((i>>j)&1)has_odd|=cnt,cnt=0;// cnt 重置
else cnt^=1; // cnt 记录每一段的奇偶
}
//! 这个必须是 has_odd | cht
//! cnt 算的是最后一段的，没有记录在has_odd 里面
vis[i]= has_odd|cnt ? 0 :1;
}
for(int i=1;i<=n;i++){
for(int j=0;j <(1<<m);j++){
for(int k=0;k<(1<<m);k++){
//转移的两个条件
if((j&k)==0 && vis[j|k]) f[i][j]+=f[i-1][k];
}
}
}
cout<<f[n][0]<<"\n";// 输出
}
return 0;
}
```
## 后记
文章整体借鉴了小蓝书《算法竞赛进阶指南》有一部分摘抄自其中。
希望可以帮助到一些初学状压的同学。