德马西亚万岁

题意：有一个n*m的地图，为0不可以站人，为1可以站人，二个人不能相邻，求合理的方案数？

思路：状压dp
dp[i][j]为第i行状态为j的方案数（状态为第i行二进制转化为十进制的值，既一个二进制为该行的整数）。
d[i]表示地图中第i行这m位取反表示的十进制。
如果该状态合法，则j&(j-1)==0，j&d[i]==0.
如果为第一行，则合法dp[i][j]为1。
如果不是第一行，则dp[i][j]= d[i-1][k] (k&j==0)
结果为 d[n][k] (k<(1<<m));

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 100000000

using namespace std;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int d[15];
ll dp[15][50005];

int main()
{
    int n, m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp, 0, sizeof(dp));
        memset(d, 0, sizeof(d));
        for(int i=1; i<=n; i++)
        {
            d[i]=0;
            for(int j=1; j<=m; j++)
            {
                int a;
                scanf("%d",&a);
                if(a==1)
                {
                    d[i]=d[i]*2;
                }
                else
                {
                    d[i]=d[i]*2+1;
                }
            }
        }
        ll z=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<(1<<m); j++)
            {
                dp[i][j]=0;
                if((j&(j<<1))!=0)
                {
                    continue;
                }
                if((j&(d[i]))!=0)
                {
                    continue;
                }
                if(i==1)
                {
                    dp[i][j]=1;
                }
                else
                {
                    for(int o=0; o<(1<<m)-1; o++)
                    {
                        if((o&j)==0)
                        {
                            dp[i][j]=(dp[i][j]+dp[i-1][o])%inf;
                        }
                    }
                }
                if(i==n)
                {
                    z=(z+dp[i][j])%inf;
                }
            }
        }
        printf("%lld\n",z);
    }
    return 0;
}