状态压缩的基础题

最艰苦朴素的算法,vaild[i]存储子集，然后暴力遍历

该方法过于艰苦，比连吃三大口苦瓜还要苦啊

#include<iostream>
#include<algorithm>

using namespace std;
const int N =14,M=1<<14;
int n,m;
vector<int> vaild[N];
int a[N];
int f[N][M];

bool check(int id,int state)
{
    for(int i=0;i<m;i++)
    {
        if(!(a[id] >>i&1)&&state>>i&1) return false;  //检测是否是坏田
        if(state>>i&1 &&state>>i+1&1) return false;  //检测同行是否冲突



    }
    return true;

}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            {
                a[i]<<=1;
                int t;
                cin>>t;
                a[i]+=t;
            }




    for(int i=1;i<=n;i++)
        for(int j=0;j<1<<m;j++)
        {
            if(check(i,j))
            vaild[i].push_back(j);
        }

        for(auto i:vaild[1])
            f[1][i] = 1;

    for(int i=2;i<=n;i++)
        for(auto j:vaild[i])
            for(auto k:vaild[i-1] )
            {
                if((j&k)==0)
                f[i][j] +=f[i-1][k];
            }

        int res =0;
    for(auto i:f[n])
    res=(res+i)%100000000;
    cout<<res<<endl;


    return 0;

}