刚学状压 DP。第一题并不是互不侵犯，也不是旅行商问题，而是这一题。
题目描述
给你一个 \(N\times M\) 的 01 矩阵，你需要在上面摆放棋子。该矩阵 0 位上不能摆放棋子，在 1 位上可以摆放，且任意两个摆放的棋子所占的位不能有公共边。求问有多少摆放方式。
特别地，不放棋子也算一种方式。答案对 \(10^8\) 取模。
数据范围：\(1\le N,M\le 10\) 。
解法
看到数据范围很小，考虑状压 DP。
这题很不毒瘤，我们可以发现棋子是四联通的，而且每层的状态可以用一个二进制数来表示，原矩阵也可以用 \(N\) 个二进制数来存储。这样每一层的状态就被压缩成了 DP 的一维。
分析可得以下信息：
- DP 状态集合：\(f[i,j]\) 表示在前 \(i\) 层的影响下，对于第 \(i\) 层状态为 \(j\) 的方案。
- DP 状态意义：\(f[i,j]\) 表示在该意义下方案的种数。
- DP 状态转移：让我们定义 \(pre\) 为我们枚举的上一行的可以使 \(j\) 这个状态合法的状态。则有 \(f[i,j] = \sum\limits^{}_{pre}f[i-1, pre]\) 。
代码实现
按照上面的方式 DP 即可，但是有一个处理到 \(n+1\) 行的小 trick。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 15;
const int maxm = 1 << 12;
const int mod = 1e8;
int n, m, g[maxn];
int f[maxn][maxm];
vector<int> state;
vector<int> head[maxm];
bool check(int state) {
return !(state & state << 1);
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 0, k; j < m; j ++)
cin >> k, g[i] |= !k << j;
for(int i = 0; i < 1 << m; i ++)
if(check(i))
state.push_back(i);
for(auto st : state)
for(auto nxt : state)
if (!(st & nxt))
head[st].push_back(nxt);
f[0][0] = 1;
for(int i = 1; i <= n + 1; i ++)
for(auto st : state)
if (!(st & g[i]))
for(auto pre : head[st])
f[i][st] = (f[i][st] + f[i - 1][pre]) % mod;
cout << f[n + 1][0];
}