德玛西亚万岁状压DP

题目范围非常小，一眼看就觉得要不是搜索要不是DP,但是是题意弄明白后就发现如果搜索的话很是麻烦，我们不能很顺利的去选择方案，然后就转换位dp，关键dp如何写，我们仔细看样列，是不是写的非常好，一行一行的就像是一个二进制串，那么是不是就可以想到状压，状压与二进制关联，然后我们就应该去判断条件，如何去写，首先 我们处理每行里面的列，j&(j>>)代表是我的这一行里面的人，(以下的01串我是代表二进制数)没有相邻的，比如101，然后>>1，就是010,然后&是不是就是0那就是说明这个情况可以满足条件，然后我们又去判断是否满足当前行的要求呢（(mp[i]&j)!=j），比如当前行是101(mp[i])，然后我们这时候弄了一个情况010(j)，然后是不是答案为0，那就说明不满足我们的条件，如果是001呢，是不是就是1，说明这一行可以安排一个也是符合题意的，然后就是在来一次判断这一行和上一行是否有相邻，k&j是否为1,具体看代码。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
ll dp[15][1<<15];
ll mp[15];
const int mo=1e8;
int main()
{
    int n,m;
    while(cin>>n>>m){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        int x;
        cin>>x;
        mp[i]=(mp[i]<<1)+x;
    }
    mse(dp,0);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<(1<<m);j++)
    {
        if(j&(j>>1)) continue;
        if((mp[i]&j)!=j) continue;
        for(int k=0;k<(1<<m);k++)
        {
            if(k&j) continue;
            dp[i][j]=(dp[i][j]+dp[i-1][k])%mo;
        }
    }
    ll ans=0;
    for(int i=0;i<(1<<m);i++)
        ans=(ans+dp[n][i])%mo;
    cout<<ans<<endl;
    }
    return 0;
}