牧场的安排(状压dp)

大意：

给N*M的棋盘，每个格子不是0就是1,1代表可以种草，否则不能。相邻两个格子不能同时种草，求种草的方案总数

要点：

• 表示第 行在状态 (用二进制数表示)的时候的方案数
• (k为不冲突的状态)
• （num为状态总数）
• 初始条件：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,dp[13][401],a[13][13],s[13];
const int mod =1e8;
vector<int> v;
int main(){
    cin>>n>>m;
    for(int i = 0;i<1<<m;i++)//从0开始才能枚举所有情况 
        if(((i<<1)&i)==0)
            v.push_back(i);
    for(int i = 1;i<=n;i++)
        for(int j = 0;j<m;j++)
            scanf("%d",&a[i][j]),s[i] = (s[i]<<1)+a[i][j];      
    dp[0][0] = 1;//方案数最少是1
    for(int i = 1;i<=n;i++)//以行作为阶段
        for(int j = 0;j<v.size();j++)//枚举第i行状态  
            if((v[j]&s[i])==v[j])//保证适合种草：v[j]每一个1位对应s[i]相同位置必须是1           
                for(int k = 0;k<v.size();k++)//枚举第i-1行状态            
                    if((v[k]&v[j])==0){
                        dp[i][j]+=dp[i-1][k];
                        dp[i][j]%=mod;
                    }                   
    ll ans = 0;
    for(int i = 0;i<v.size();i++)
        ans = (ans+dp[n][i])%mod;
    cout<<ans;
    return 0;
}