【luogu P1879 [USACO06NOV]玉米田Corn Fields】 题解

题目链接：https://www.luogu.org/problemnew/show/P1879

状压DP。

设dp[i][j]表示第i行，状态为j的方案数

初始dp[0][0] = 1

这样一共12行12列，最多1<<12。

这样转移时，只要满足上下没有两个1，这两行分别满足没有相邻1。

加法原理转移。

\(j&k==0\)

$ dp[i][j] += dp[i-1][k] $

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int maxn = 5000;

const int mod = 100000000;

ll a[20][maxn], dp[20][maxn], n, m, b[20], ans, is[maxn];

int main()

{

	cin>>n>>m;

	for(ll i = 1; i <= n; i++)

		for(ll j = 1; j <= m; j++) cin>>a[i][j];

	for(ll i = 1; i <= n; i++)

		for(ll j = 1; j <= m; j++)

		if(a[i][j]) b[i] += (1<<(m-j+1));

	for(ll i = 1; i <= n; i++) b[i] >>= 1;

	for(ll i = 0; i < (1 << m); i++)

	if((i&(i<<1)) == 0 && (i&(i>>1)) == 0) is[i] = 1;

	dp[0][0] = 1;

	for(ll i = 1; i <= n; i++)

	{

		for(ll j = 0; j < (1 << m); j++)

		{

			if(is[j] && ((j & b[i]) == j))

			for(ll k = 0; k < (1 << m); k++)

			{

				if((j & k) == 0)

				dp[i][j] = (dp[i][j] + dp[i-1][k])%mod;

			}

		}

	}

	for(ll i = 0; i < (1 << m); i++) ans = (ans + dp[n][i]) % mod;

	cout<<ans%mod;

}