德玛西亚万岁

题解：

由于本题数据范围较小，很容易想到状态压缩Dp的方式进行模拟，我们让dp[i][S]表示第i行的勇士状态为S(将s拆成二进制位，1表示该为有勇士)时的方案数，那么最后总的答案就为 ,所以直接枚举就可以啦！
注意要过滤掉其中一些非法状态，就是题目所说的那些，为了检测方便，可以将每行的状态转换为一个二进制数，直接位运算判断即可

代码

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const  ll inf  = 0x3f3f3f3f3f3f3f3f;
const int mod  = 100000000;
const int maxn = 1e6 + 4;
const int N    = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1);
ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}

ll dp[13][(1<<12)+10];
int a[13],n,m;

int main() {
    //freopen("RACE input.in","r",stdin);
    while(~scanf("%d%d",&n,&m)) {
        memset(dp,0,sizeof dp);
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++) {
            for(int j=0;j<m;j++) {
                int x;scanf("%d",&x);
                a[i]|=(x<<j);
            }
        }
        int limit=1<<m;
        dp[0][0]=1;
        for(int i=1;i<=n;i++) {
            for(int x=0;x<limit;x++) {
                if((x&a[i])!=x) continue;
                if(x&(x>>1)) continue;
                for(int s=0;s<limit;s++) {
                    if(s&x) continue;
                    dp[i][x]=(dp[i-1][s]+dp[i][x])%mod;
                }
            }
        }
        ll ans=0;
        for(int i=0;i<limit;i++) ans=(ans+dp[n][i])%mod;
        printf("%lld\n",ans);
    }
}