题目描述

农夫约翰的土地由 $M \times N$ 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 1 行包含两个整数 $M$ 和 $N$。

第 2..M+1 行：每行包含 $N$ 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式

输出总种植方法对 $10^8$ 取模后的值。

样例

2 3
1 1 1
0 1 0

9

样例解释

土地状况

$M=2, N=3$ 土地：

1 1 1
0 1 0

1 表示肥沃，0 表示不育（不能种植）。

种植规则

1. 只能在肥沃的土地上种植。
2. 相邻（有公共边）的土地不能同时种植。

计算种植方案数

我们枚举所有可能的种植方案。

将土地格子编号（从左到右，从上到下）： (1,1)=1, (1,2)=1, (1,3)=1 (2,1)=0, (2,2)=1, (2,3)=0

只有肥沃的格子才能种，所以可种植的格子： (1,1), (1,2), (1,3), (2,2)。

我们需要选择这些格子的一个子集，使得没有两个选中的格子相邻。

枚举方案

用二进制表示每行的种植状态（1 表示种，0 表示不种），注意只能种在肥沃格子上。

第一行：三个格子都肥沃，可能的状态（3位二进制）： 000, 001, 010, 011, 100, 101, 110, 111。 但需要满足相邻不能同时种：即二进制中不能有相邻的 1。

• 000: 有效
• 001: 有效（只有最后一个种）
• 010: 有效
• 011: 无效（后两位相邻）
• 100: 有效
• 101: 有效（第一位和第三位种，中间不种，不相邻）
• 110: 无效（前两位相邻）
• 111: 无效

所以第一行有效状态：000, 001, 010, 100, 101。

第二行：只有中间格子 (2,2) 肥沃，其他不育。 所以种植状态只能是 0 或 1（只有一列？第二行有3列，但只有第二列肥沃，所以状态只有两种：000 和 010？注意状态要对应整行，不育的格子不能种，所以状态中对应不育格子的位必须是 0。因此第二行的可能状态：000 和 010（因为只有第二列可以种，第一列和第三列必须为 0）。 同时，状态自身不能有相邻的 1（但这里只有一个 1，所以都满足）。

行间相邻检查

相邻行同一列的格子不能同时种。

我们枚举所有组合： 第一行状态有 5 种，第二行状态有 2 种，共 10 种组合，检查行间相邻：

设第一行状态 s1，第二行状态 s2，需要满足 (s1 & s2) == 0（同一列不能同时为 1）。

列举：

1. s1=000 (0), s2=000 (0) → 0 & 0 = 0，有效。
2. s1=000 (0), s2=010 (2) → 0 & 2 = 0，有效。
3. s1=001 (1), s2=000 → 1 & 0 = 0，有效。
4. s1=001 (1), s2=010 (2) → 1 & 2 = 0，有效。
5. s1=010 (2), s2=000 → 2 & 0 = 0，有效。
6. s1=010 (2), s2=010 (2) → 2 & 2 = 2 ≠ 0，无效。
7. s1=100 (4), s2=000 → 4 & 0 = 0，有效。
8. s1=100 (4), s2=010 (2) → 4 & 2 = 0，有效。
9. s1=101 (5), s2=000 → 5 & 0 = 0，有效。
10. s1=101 (5), s2=010 (2) → 5 & 2 = 0，有效。

无效的只有第 6 种，所以有效组合 9 种。

对应种植方案：

1. 都不种。
2. 只种 (2,2)。
3. 只种 (1,3)。
4. 种 (1,3) 和 (2,2)（不相邻，因为 (1,3) 和 (2,2) 斜对角，不算相邻，只有上下左右相邻才禁止。这里 (1,3) 和 (2,3) 相邻，但 (2,3) 不育，所以没问题）。
5. 只种 (1,2)。
6. 无效。
7. 只种 (1,1)。
8. 种 (1,1) 和 (2,2)（不相邻）。
9. 种 (1,1) 和 (1,3)。
10. 种 (1,1), (1,3), (2,2)（检查相邻：(1,1) 和 (1,3) 不相邻，(1,3) 和 (2,2) 斜对角不相邻，(1,1) 和 (2,2) 斜对角不相邻，所以有效）。

所以总共 9 种方案，输出 9。

数据范围

• $1 \le M, N \le 12$

算法分析

这是一个典型的状态压缩动态规划问题，类似“玉米田”或“炮兵阵地”问题。

状态表示

由于 $N \le 12$，我们可以用二进制数表示一行的种植状态（1 表示种，0 表示不种）。

设 $dp[i][s]$ 表示前 $i$ 行，且第 $i$ 行的种植状态为 $s$ 时的总方案数。

状态转移

$dp[i][s] = \sum_{prev} dp[i-1][prev]$，其中 $prev$ 是第 $i-1$ 行的状态，满足：

1. $s$ 是合法的：即 $s$ 中不能有相邻的 1（因为同一行相邻格子不能种）。
2. $s$ 只能种在肥沃的土地上：即对于第 $i$ 行的土地状况 $row[i]$（也是一个二进制数，肥沃为 1，不育为 0），必须满足 $(s \& ~row[i]) == 0$（即 $s$ 中为 1 的位在 $row[i]$ 中也必须为 1）。
3. $prev$ 和 $s$ 不能有同一列为 1：即 $(s \& prev) == 0$。

初始化

$dp[0][0] = 1$（第 0 行没有土地，状态只能为 0）。

最终答案

所有 $dp[M][s]$ 的和，对 $10^8$ 取模。

优化

• 预处理所有合法的行状态（即没有相邻 1 的状态），最多 $2^N$ 个，对于 $N=12$ 是 4096，但合法状态少得多（斐波那契数列增长，约 377 个）。
• 对于每一行，再从中筛选出符合该行土地肥沃条件的状态。
• 转移时枚举当前行状态和上一行状态，复杂度 $O(M \times |S|^2)$，其中 $|S|$ 是合法状态数，约 400，$M \le 12$，计算量很小。

实现步骤

1. 读入 $M, N$ 和土地矩阵。
2. 将每行的土地状况压缩为一个整数 $row[i]$：从左到右，第 $j$ 位为 1 表示肥沃。
3. 预处理所有合法状态 $valid$：遍历 $0$ 到 $2^N-1$，筛选出没有相邻 1 的状态（即 (s & (s >> 1)) == 0）。
4. 对于每一行 $i$，从 $valid$ 中筛选出符合该行土地的状态 $state[i]$：满足 (s & ~row[i]) == 0。
5. 动态规划：
   • $dp[0][0] = 1$。
   • 对于 $i$ 从 1 到 $M$：
     • 对于当前行状态 $s \in state[i]$：
       • $dp[i][s] = \sum_{prev \in state[i-1]} dp[i-1][prev]$，其中 $(s \& prev) == 0$。
6. 答案 $ans = \sum_{s \in state[M]} dp[M][s] \mod 10^8$。

复杂度

• 状态数 $O(2^N)$，$N \le 12$，可接受。
• 转移 $O(M \times |S|^2)$，$|S| \approx 400$，$M \le 12$，计算量约 $12 \times 400^2 = 1.92 \times 10^6$，很快。

总结

本题是状态压缩 DP 的入门题，关键点在于将行状态压缩为二进制，并检查合法性。