德玛西亚万岁（状压dp）

由于状压dp是在位运算的基础上进行的，所以先了解一下一些基础的位运算操作
我们把每一行的状态用二进制储存起来

    ll x=read();
        a[i]=(a[i]<<1)+x;

假如输入的是101
那么a[i]的变化过程为
a[i]=1
a[i]=2
a[i]=5
5的二进制刚好是101
解决了储存问题，在解决图上冲突问腿
有一个二进制数字x

if(x&x<<1)

可以判断是否有相邻的两者相同
还有一种冲突是当前状态j和地图状态不符合
假如地图状态（第i行）a[i]=1011
j1=1100（不合法）
j2=1000(合法)

那么j1&a[i]=1000
j2&a[i]=1000
所以我们可以用

    if((j&a[i])!=j) continue;

判断当前状态是否和地图状态冲突
上下两行的状态冲突判断比较简单
不能同时为1 ，（对于某一位）

    if(k&j) continue;

代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=5e5+7;
const ll mod = 100000000;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,dp[16][30000],a[16];
int UpMing() {
    while(scanf("%lld%lld",&n,&m)!=EOF) {
        mst(a,0);
        for(int i=1 ; i<=n ; i++)
            for(int j=0 ; j<m ; j++) {
                ll x=read();
                a[i]=(a[i]<<1)+x;
            }
        mst(dp,0);
        dp[0][0]=1;

        for(int i=1 ; i<=n ; i++) {
            for(int j=0 ; j<(1<<m); j++) {
                if((j&a[i])!=j) continue;
                if(j&(j<<1))  continue;
                for(int k=0 ; k<(1<<m); k++) {
                    if(k&j) continue;
                    dp[i][j]+=dp[i-1][k]%mod,dp[i][j]%=mod;
                }
            }
        }
        ll res=0;
        for(int i=0 ; i<(1<<m); i++)
            res+=dp[n][i]%mod,res%=mod;
        out(res);
        puts(" ");
    }
    Accept;
}
/*

*/