分析
考虑状压dp在(nleq 21)的情况下会TLE，
设(dp[n][m][S])表示当前正在处理((n,m))这个格子
并且轮廓线状态为(S)的方案数，
考虑可行状态最多存在一对相邻的1，实际上状态最多为(1.3*10^5)个，
一行的第一个格子不需要考虑左边是否已经填了1
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
const int N=130011,mod=100000000;
int dp[N],f[N],tot,b[N],rk[2097152],n,m,al,ans;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed mo(int x,int y){return x+y>=mod?x+y-mod:x+y;}
signed main(){
freopen("cowfood.in","r",stdin);
freopen("cowfood.out","w",stdout);
n=iut(),m=iut(),al=(1<<m)-1;
for (rr int i=0;i<al;++i){
rr int now=i&(i<<1);
if (!(now&(now-1)))
b[++tot]=i,rk[i]=tot;
}
dp[1]=1;
for (rr int i=1;i<=n;++i){
rr int now=0;
for (rr int j=0;j<m;++j) now|=iut()<<j;
for (rr int j=1;j<=tot;++j){
rr int t0=rk[b[j]&(al^1)],t1=rk[b[j]|1];
if (!(b[j]&1)) f[j]=mo(dp[t0],dp[t1]);
else if (now&1) f[j]=dp[t0];
else f[j]=0;
}
memcpy(dp,f,sizeof(int)*(tot+1));
for (rr int k=1;k<m;++k){
for (rr int j=1;j<=tot;++j){
rr int t0=rk[b[j]&(al^(1<<k))],t1=rk[b[j]|(1<<k)];
if (!((b[j]>>k)&1)) f[j]=mo(dp[t0],dp[t1]);
else if (!((b[j]>>(k-1))&1)&&((now>>k)&1)) f[j]=dp[t0];
else f[j]=0;
}
memcpy(dp,f,sizeof(int)*(tot+1));
}
}
for (rr int i=1;i<=tot;++i) ans=mo(ans,dp[i]);
return !printf("%d",ans);
}