原题链接：https://www.luogu.com.cn/problem/P1879
题意解读：在m*n的区域种玉米，能种的是1不能种的是0，要求玉米不能种在相邻格子，求一共有多少种法，模100000000。
解题思路：
用状态压缩来表示一行玉米的种植情况，二进制中1表示种了，0表示没种。
对于一行状态，可以判断其合法性：相邻不能有连续1，在不能种的格子不能有1。
状态转移也很简单，通过枚举两行的合法状态，然后看两行状态是否存在上下相邻的1，不存在则可以转移。
状态表示：设f[i][j]表示前i行已种完，且第i行的状态为j的方案数
初始化：f[0][0] = 1，不种也是一种方案
状态转移：枚举所有第i行的状态j，枚举所有第i-1行的状态k，f[i][j] += f[i - 1][k]
结果：多枚举一行，枚举到第m+1行，答案是f[m + 1][0]
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 15, MOD = 1e8;int mask[N];
int f[N][1 << 12];
vector<int> stat; //所有合法的状态
vector<int> mp[1 << 12]; //所有合法的状态转移
int m, n;int main()
{cin >> m >> n;for(int i = 1; i <= m; i++){for(int j = 0; j < n; j++){int x;cin >> x;if(x == 0) mask[i] |= (1 << j);}}//找到所有合法状态for(int i = 0; i < 1 << n; i++){if(i & i << 1) continue; //存在左右相邻的1stat.push_back(i);}//找到所有合法的状态转移for(auto i : stat){for(auto j : stat){if(i & j) continue; //存在上下相邻的1mp[i].push_back(j);}}f[0][0] = 1;for(int i = 1; i <= m + 1; i++){for(auto j : stat){if(mask[i] & j) continue; //第i行存在不能种的土地for(auto k : mp[j]){if(mask[i - 1] & k) continue; //第i - 1行存在不能种的土地f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;}}}cout << f[m + 1][0];return 0;
}