这道题跟互不侵犯差不多，但是数据范围更大了

对于状态压缩dp，提前枚举出转移是一种很好的优化

然后对于转移也需要仔仔细细的分析，如同期望dp

#include
    
     #include
     
      #include
      
       const int mod=1e8;int map[20];long long f[2][1<<12];int b[400],tot;int main(){    int n,m;    scanf("%d%d",&n,&m);    int a;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            scanf("%d",&a);            a^=1;            map[i]=(map[i]<<1)+a;        }    for(int i=0;i<(1<
       
        >1)))    b[++tot]=i;    for(int i=1;i<=tot;i++)        if(!(map[1]&b[i]))            f[1][b[i]]=1;    for(int i=2;i<=n;i++)        for(int j=1;j<=tot;j++)        {            f[i&1][b[j]]=0;            if(!(map[i]&b[j]))                for(int k=1;k<=tot;k++)                    if(!(b[j]&b[k])&&!(map[i-1]&b[k]))                        f[i&1][b[j]]=(f[i&1][b[j]]+f[(i&1)^1][b[k]])%mod;        }    long long ans=0;    for(int i=1;i<=tot;i++)        ans=(ans+f[n&1][b[i]])%mod;    printf("%lld",ans);}