Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Line 1: Two space-separated integers: M and N 
Lines 2.. M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

2 3

1 1 1

0 1 0

9

题意：一个n*m的玉米田，为1的是不可种植地带，为0才可以种植，有一个约束条件，就是相邻的不能同时种植，现在要你求有多少种植方式

思路：状压一般我们要去关注他的数据范围，因为与二进制有关，所以一般范围都会在32以内，然后我们首先向一行内满足状态的有多少个
这时候就必须熟悉位运算操作，我们把一行当作一个二进制，判断相邻即 x&(x<<1)  这是一行内满足要求的个数
但是这个我们还没有考虑图中的不可种植地带，这个时候我们就必须把这些状态去与图所比较，看是否满足要求，但是我们判断是够冲突，一般
只能去考虑二进制1是否有冲突，所以我把原图的0和1颠倒
已经把行冲突的考虑完了，现在考虑列冲突，因为我们同列相邻的为1也会发生冲突，所以我们把最新的一行的状态与前一行比较
dp[i][j]代表前i行中第i行放第j中状态满足要求的个数

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<map>

#define maxn 20

#define mod 1000000000

using namespace std;

typedef long long ll;

ll n,m;

ll dp[maxn][];

ll a[maxn];

ll top;

ll prime[];

ll num;

ll ok(ll x)//判断相邻是否满足要求

{

    if(x&(x<<)) return ;

    return ;

}

void init()//预处理出一行内所有满足要求的状态

{

    top=<<m;

    for(int i=;i<top;i++)

    {

        if(ok(i))

            prime[num++]=i;

    }

}

int fit(ll x,ll z) //判断第x行与z状态是否有冲突，即判断行内满足不相邻的状态是否与图有冲突

{

    if(a[x]&z) return ;

    return ;

}

int main()

{

    cin>>n>>m;

    init();

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            ll x;

            cin>>x;

            if(x==)//因为要用来判断会不会与图发生冲突，改成二进制1为不能放

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

        }

    }

    for(int i=;i<num;i++)//看所有的状态是否满足第一行要求

    {

        if(fit(,prime[i])) dp[][i]=;

    }

    for(int i=;i<=n;i++)

    {

        for(int j=;j<num;j++)

        {

            if(!fit(i,prime[j])) continue;

            for(int k=;k<num;k++)

            {

                if(prime[j]&prime[k]) continue;

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

            }

         }

    }

    ll sum=;

    for(int i=;i<num;i++)

    {

        sum=(sum+dp[n][i])%mod;

    }

    cout<<sum;

}