每日一题 6.3 德玛西亚万岁

二进制枚举+状压dp
一开始我是没想到的 我还以为是搜索....
接受了社会的毒打后 发现看成状压dp还挺好写的
每一层的合法状态可由上一层的所有合法状态得到 而每一层哪些状态合法也是比较容易算出来的
代码有详细注释

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e8;
const int N = 13;
const int INF = 1e5;
ll n,m,a,dp[N][1<<N],s[N],t;
int main()
{
       ios::sync_with_stdio(false);
       while(cin>>n>>m)
       {
            for(int i=1;i<=n;++i)
            {
               for(int j=1;j<=m;++j)
               {
                   cin>>a;
                   s[i]=(s[i]<<1)+a;
               }
            }
            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((j&s[i])!=j) continue;
                   for(int k=0;k<1<<m;++k)
                   {
                     if(k&j) continue;
                     dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
                   }
               }
            }
            ll ans=0;
            for(int i=0;i<1<<m;++i) ans=(ans+dp[n][i])%mod;
            cout<<ans<<endl;
            memset(dp,0,sizeof(dp));
       }

    return 0;
}