开一个扫盲计划。oiwiki 从左到右把完全不会的看一遍。
于是现在来开插头。其实插头如果理解了是个什么东西的话还是比较套路的。
不详细讲了，大概可以看洛谷第二篇题解的图，画的很好。我这没条件画图就鸽了。
要说的话大概分若干情况讨论：（代码中 \(0\) 为无插头，\(1\) 为左括号，\(2\) 为右括号）
- 是障碍，不能有左插头或上插头。
- 没有插头，需要新建右插头和下插头。
- 有左无上，左延续到右或下。
- 有上无左，上延续到右或下。
- 左为左括号，上为左括号：扫一遍找到上匹配的右括号改成左括号。
- 左为右括号，上为右括号：扫一遍找到左匹配的左括号改成右括号。
- 左为右括号，上为左括号：直接连起来，没有往外的插头。
- 左为左括号，上为右括号：连接成回路，必须是终点，如果是就统计答案，不是则不合法。
还有一点是行间转移的时候要在最前面新建一个位置没有插头，作为新的左轮廓线。同时我们采用四进制方便转移。
就上个注释版板子代码吧。用的四进制状压括号表示法。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int mod=10007;
int n,m,ans;
char s[20][20];
bool a[20][20];
struct HS{
int head[mod+10],next[20010],st[20010],t;
int dp[20010];
void ins(int s,int val){
int x=s%mod;
for(int i=head[x];i;i=next[i]){
if(st[i]==s){
dp[i]+=val;return;
}
}
st[++t]=s;dp[t]=val;next[t]=head[x];head[x]=t;
}
void clear(){
t=0;memset(head,0,sizeof(head));
}
void roll(){
for(int i=1;i<=t;i++)st[i]<<=2;
}
}hs[2];
signed main(){
scanf("%lld%lld",&n,&m);
int cur=0,endx,endy;
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++)if(s[i][j]=='.')a[i][j]=true,endx=i,endy=j;
}
hs[0].dp[1]=hs[0].t=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cur^=1;hs[cur].clear();
for(int k=1;k<=hs[cur^1].t;k++){
int s=hs[cur^1].st[k],l=(s>>(j-1<<1))&3,r=(s>>(j<<1))&3;//l左插头 r上插头
if(!a[i][j]){
if(!l&&!r)hs[cur].ins(s,hs[cur^1].dp[k]);continue;//障碍 不能有插头
}
if(!l&&!r){//没有插头 向右下新增插头
if(!a[i][j+1]||!a[i+1][j])continue;
hs[cur].ins(s^(1<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]);//1左括号 2右括号
}
if(l&&!r){
if(a[i][j+1])hs[cur].ins(s^(l<<(j-1<<1))^(l<<(j<<1)),hs[cur^1].dp[k]);//有左无上 消掉下新增右
if(a[i+1][j])hs[cur].ins(s,hs[cur^1].dp[k]);//本来就有下
}
if(!l&&r){
if(a[i][j+1])hs[cur].ins(s,hs[cur^1].dp[k]);//同上
if(a[i+1][j])hs[cur].ins(s^(r<<(j<<1))^(r<<(j-1<<1)),hs[cur^1].dp[k]);
}
if(l==1&&r==1){//两个左括号 可以合并
int ret=1;
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(1<<(p<<1));break;//括号匹配 找到上插头匹配的右括号变为左括号
}
}
hs[cur].ins(s^(1<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]);//去掉两个插头
}
if(l==2&&r==2){
int ret=1;
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(2<<(p<<1))^(1<<(p<<1));break;//同上 找到左插头匹配的左括号变为右括号
}
}
hs[cur].ins(s^(2<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]);//去掉两个插头
}
if(l==2&&r==1){
hs[cur].ins(s^(2<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]);//一右一左 可以直接闭合
}
if(l==1&&r==2&&i==endx&&j==endy)ans+=hs[cur^1].dp[k];//一左一右 必须结尾
}
}
hs[cur].roll();//行间转移 前面补一个空插头0
}
printf("%lld\n",ans);
return 0;
}
调试建议静态查错。一是你看着这玩意会丧失 gdb 和输出中间变量的动力。二是这玩意逻辑通常比较清晰，只要你逻辑没错那通常能比较快地跳出来。
[HNOI2007]神奇游乐园
和板子不同，我们现在面临两个问题。
- 可以不全部经过。这个可以在没有插头时通过不新建插头的方式来处理，统计答案的时候也不限定在最后一格了。
- 权值。我们插头 dp 通常把转移写到哈希表里，前面是方案数，所以累加，这里求最大值，取 \(\max\) 就好了。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=10007;
int n,m,ans=-0x3f3f3f3f,val[110][20];
bool a[110][20];
struct HS{
int head[mod+10],next[300010],st[300010],t;
int dp[300010];
void ins(int s,int val){
int x=s%mod;
for(int i=head[x];i;i=next[i]){
if(st[i]==s){
dp[i]=max(dp[i],val);return;//这里改成取max
}
}
st[++t]=s;dp[t]=val;next[t]=head[x];head[x]=t;
}
void clear(){
t=0;memset(head,0,sizeof(head));memset(dp,-0x3f,sizeof(dp));
}
void roll(){
for(int i=1;i<=t;i++)st[i]<<=2;
}
}hs[2];
signed main(){
scanf("%d%d",&n,&m);
int cur=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)scanf("%d",&val[i][j]),a[i][j]=true;
}
hs[0].dp[1]=0;hs[0].t=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cur^=1;hs[cur].clear();
for(int k=1;k<=hs[cur^1].t;k++){
int s=hs[cur^1].st[k],l=(s>>(j-1<<1))&3,r=(s>>(j<<1))&3;
if(!l&&!r){
hs[cur].ins(s,hs[cur^1].dp[k]);//可以不加插头
if(a[i][j+1]&&a[i+1][j])hs[cur].ins(s^(1<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l&&!r){
if(a[i][j+1])hs[cur].ins(s^(l<<(j-1<<1))^(l<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
if(a[i+1][j])hs[cur].ins(s,hs[cur^1].dp[k]+val[i][j]);
}
if(!l&&r){
if(a[i][j+1])hs[cur].ins(s,hs[cur^1].dp[k]+val[i][j]);
if(a[i+1][j])hs[cur].ins(s^(r<<(j<<1))^(r<<(j-1<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==1&&r==1){
int ret=1;
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(1<<(p<<1));break;
}
}
hs[cur].ins(s^(1<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==2&&r==2){
int ret=1;
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(2<<(p<<1))^(1<<(p<<1));break;
}
}
hs[cur].ins(s^(2<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==2&&r==1){
hs[cur].ins(s^(2<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==1&&r==2){
if(s==((1<<(j-1<<1))^(2<<(j<<1))))ans=max(ans,hs[cur^1].dp[k]+val[i][j]);
}
}
}
hs[cur].roll();
}
printf("%d\n",ans);
return 0;
}
BZOJ2310 ParkII
这次变成了一条路径。这样就比上边又多了一些情况，因为不要求两边闭合。
对于一条路径的问题，我们通常通过添加独立插头的方式处理。独立插头就是不与其他插头匹配的插头（代码中为 \(3\)）。
我们有如下情况：（设 \(l\) 为左插头，\(r\) 为上插头）
- \(l=0,r=0\)：我们有三种选择：不添加插头，添加一对插头，或者选一个方向添加独立插头。
- \(l\neq 0,r=0\)：仍然可以使 \(l\) 代表的插头选一个方向延伸。另外我们多出了两个选择：
- 如果 \(l=3\)，那么可以把 \(l\) 断掉并统计答案。
- 否则，可以把 \(l\) 断掉，把和 \(l\) 匹配的插头改为独立插头。
- \(l=0,r\neq 0\)：同上。
- \(l=1,r=1\)：两个左括号，仍然是连起来并找到匹配的右括号改成左括号。
- \(l=2,r=2\)：两个右括号，仍然是连起来并找到匹配的左括号改成右括号。
- \(l=2,r=1\)：仍然可以直接连起来。
- \(l=1,r=2\)：注意到这时我们形成了回路，所以这个状态是不合法的。
- \(l=3,r\neq 3,r\neq 0\)：可以连接 \(l,r\)，然后把 \(r\) 匹配的插头改成独立插头。
- \(l\neq 3,l\neq 0,r=3\)：同上。
代码实现上实际上可以把找匹配的括号这个过程封装成一个函数。我比较懒没封装导致代码巨大长。别人都三四 k 我 8k。（把行前空格变成 tab 少了 3k）
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=10007;
int n,m,ans=-0x3f3f3f3f,val[110][20];
bool a[110][20];
struct HS{
int head[mod+10],next[300010],st[300010],t;
int dp[300010];
void ins(int s,int val){
int x=s%mod;
for(int i=head[x];i;i=next[i]){
if(st[i]==s){
dp[i]=max(dp[i],val);return;
}
}
st[++t]=s;dp[t]=val;next[t]=head[x];head[x]=t;
}
void clear(){
t=0;memset(head,0,sizeof(head));memset(dp,-0x3f,sizeof(dp));
}
void roll(){
for(int i=1;i<=t;i++)st[i]<<=2;
}
}hs[2];
signed main(){
scanf("%d%d",&n,&m);
int cur=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)scanf("%d",&val[i][j]),a[i][j]=true;
}
hs[0].dp[1]=0;hs[0].t=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cur^=1;hs[cur].clear();
for(int k=1;k<=hs[cur^1].t;k++){
int s=hs[cur^1].st[k],l=(s>>(j-1<<1))&3,r=(s>>(j<<1))&3;
if(!l&&!r){
hs[cur].ins(s,hs[cur^1].dp[k]);//不走这格
if(a[i][j+1]&&a[i+1][j])hs[cur].ins(s^(1<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);//一下一右
if(a[i][j+1])hs[cur].ins(s^(3<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);//独立插头右
if(a[i+1][j])hs[cur].ins(s^(3<<(j-1<<1)),hs[cur^1].dp[k]+val[i][j]);//独立插头下
}
if(l&&!r){
if(a[i][j+1])hs[cur].ins(s^(l<<(j-1<<1))^(l<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);//右走
if(a[i+1][j])hs[cur].ins(s,hs[cur^1].dp[k]+val[i][j]);//下走
if(l==3){
if(s==(3<<(j-1<<1)))ans=max(ans,hs[cur^1].dp[k]+val[i][j]);//插头停止 更新答案
if(a[i][j+1])hs[cur].ins(s^(3<<(j-1<<1))^(3<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);//插头向右
if(a[i+1][j])hs[cur].ins(s,hs[cur^1].dp[k]+val[i][j]);//插头向下
}
else{
int ret=1;//断掉插头 前或后边匹配的插头变成独立插头
if(l==1){
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(3<<(p<<1));break;
}
}
}
else{
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(1<<(p<<1))^(3<<(p<<1));break;
}
}
}
hs[cur].ins(s^(l<<(j-1<<1)),hs[cur^1].dp[k]+val[i][j]);
}
}
if(!l&&r){
if(a[i][j+1])hs[cur].ins(s,hs[cur^1].dp[k]+val[i][j]);//右走
if(a[i+1][j])hs[cur].ins(s^(r<<(j<<1))^(r<<(j-1<<1)),hs[cur^1].dp[k]+val[i][j]);//下走
if(r==3){
if(s==(3<<(j<<1)))ans=max(ans,hs[cur^1].dp[k]+val[i][j]);//插头停止 更新答案
if(a[i][j+1])hs[cur].ins(s,hs[cur^1].dp[k]+val[i][j]);//插头向右
if(a[i+1][j])hs[cur].ins(s^(3<<(j-1<<1))^(3<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);//插头向下
}
else{
int ret=1;
if(r==1){//断掉上插头 把匹配的变成独立插头
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(3<<(p<<1));break;
}
}
}
else{
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(1<<(p<<1))^(3<<(p<<1));break;
}
}
}
hs[cur].ins(s^(r<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
}
if(l==1&&r==1){//两个左括号 找到右括号改一下
int ret=1;
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(1<<(p<<1));break;
}
}
hs[cur].ins(s^(1<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==2&&r==2){//两个右括号 找到左括号改一下
int ret=1;
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(2<<(p<<1))^(1<<(p<<1));break;
}
}
hs[cur].ins(s^(2<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==2&&r==1){//连起来
hs[cur].ins(s^(2<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l==3&&r==3){
if(s==((3<<(j-1<<1))^(3<<(j<<1))))ans=max(ans,hs[cur^1].dp[k]+val[i][j]);//粘起来则更新答案
}
if(l==3&&r!=3&&r!=0){//连接l和r 把r匹配的变成独立插头
int ret=1;
if(r==1){//断掉下插头 把匹配的变成独立插头
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(3<<(p<<1));break;
}
}
}
else{
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(1<<(p<<1))^(3<<(p<<1));break;
}
}
}
hs[cur].ins(s^(3<<(j-1<<1))^(r<<(j<<1)),hs[cur^1].dp[k]+val[i][j]);
}
if(l!=3&&l!=0&&r==3){
int ret=1;
if(l==1){//断掉右插头 把匹配的变成独立插头
for(int p=j+1;p<=m;p++){
int val=(s>>(p<<1))&3;
if(val==1)ret++;
if(val==2)ret--;
if(!ret){
s^=(2<<(p<<1))^(3<<(p<<1));break;
}
}
}
else{
for(int p=j-2;p>=0;p--){
int val=(s>>(p<<1))&3;
if(val==1)ret--;
if(val==2)ret++;
if(!ret){
s^=(1<<(p<<1))^(3<<(p<<1));break;
}
}
}
hs[cur].ins(s^(3<<(j<<1))^(l<<(j-1<<1)),hs[cur^1].dp[k]+val[i][j]);
}
}
}
hs[cur].roll();
}
printf("%d\n",ans);
return 0;
}
两个不太一样的题
[SCOI2011]地板
这回让你用 L 型地板铺棋盘。所以我们应当改变插头的定义。
注意到 L 型只会转弯一次，因此可以设 \(1\) 为没转弯的，\(2\) 为转过弯的。
那么转移就是分讨了：
- 障碍：不能有插头。
- 没有插头：可以下右加两个 \(2\)，也可以选一个方向加一个 \(1\)。
- 一个 \(1\)：可以延伸或拐弯变成 \(2\)。
- 一个 \(2\)：可以延伸或者停止。
- 两个 \(1\)：可以接起来。
挺好写的。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int mod=20110520,Mod=10007;
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
int n,m,ans;
char s[110][110];
bool a[110][110];
struct HS{
int head[Mod+10],next[300010],st[300010],t;
int dp[300010];
void ins(int s,int val){
int x=s%Mod;
for(int i=head[x];i;i=next[i]){
if(st[i]==s){
dp[i]=add(dp[i],val);return;
}
}
st[++t]=s;dp[t]=val;next[t]=head[x];head[x]=t;
}
void clear(){
t=0;memset(head,0,sizeof(head));
}
void roll(){
for(int i=1;i<=t;i++)st[i]<<=2;
}
}hs[2];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
int cur=0,endx,endy;
if(n>=m){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)if(s[i][j]=='_')a[i][j]=true,endx=i,endy=j;
}
}
else{
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)if(s[j][i]=='_')a[i][j]=true,endx=i,endy=j;
}
swap(n,m);
}
hs[0].dp[1]=hs[0].t=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cur^=1;hs[cur].clear();
for(int k=1;k<=hs[cur^1].t;k++){
int s=hs[cur^1].st[k],l=(s>>(j-1<<1))&3,r=(s>>(j<<1))&3;
if(!a[i][j]){
if(!l&&!r)hs[cur].ins(s,hs[cur^1].dp[k]);continue;
}
if(!l&&!r){
if(a[i+1][j]&&a[i][j+1])hs[cur].ins(s^(2<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]);
if(a[i+1][j])hs[cur].ins(s^(1<<(j-1<<1)),hs[cur^1].dp[k]);
if(a[i][j+1])hs[cur].ins(s^(1<<(j<<1)),hs[cur^1].dp[k]);
}
if(l==1&&!r){
if(a[i][j+1])hs[cur].ins(s^(1<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]);
if(a[i+1][j])hs[cur].ins(s^(1<<(j-1<<1))^(2<<(j-1<<1)),hs[cur^1].dp[k]);
}
if(!l&&r==1){
if(a[i+1][j])hs[cur].ins(s^(1<<(j<<1))^(1<<(j-1<<1)),hs[cur^1].dp[k]);
if(a[i][j+1])hs[cur].ins(s^(1<<(j<<1))^(2<<(j<<1)),hs[cur^1].dp[k]);
}
if(l==2&&!r){
if(i==endx&&j==endy)ans=add(ans,hs[cur^1].dp[k]);
hs[cur].ins(s^(2<<(j-1<<1)),hs[cur^1].dp[k]);
if(a[i][j+1])hs[cur].ins(s^(2<<(j-1<<1))^(2<<(j<<1)),hs[cur^1].dp[k]);
}
if(!l&&r==2){
if(i==endx&&j==endy)ans=add(ans,hs[cur^1].dp[k]);
hs[cur].ins(s^(2<<(j<<1)),hs[cur^1].dp[k]);
if(a[i+1][j])hs[cur].ins(s^(2<<(j<<1))^(2<<(j-1<<1)),hs[cur^1].dp[k]);
}
if(l==1&&r==1){
if(i==endx&&j==endy)ans=add(ans,hs[cur^1].dp[k]);
hs[cur].ins(s^(1<<(j-1<<1))^(1<<(j<<1)),hs[cur^1].dp[k]);
}
}
}
hs[cur].roll();
}
printf("%d\n",ans);
return 0;
}
[Code+#3]白金元首与莫斯科
题意：\(1\times 2\) 骨牌覆盖，有障碍，问每个地方是障碍时铺的方案数。
骨牌覆盖实际上也可以轮廓线 dp。把横放看成左右插头，竖放看成上下插头就行了。而且插头只有两种。
这个题如果暴力枚举每个地方是障碍然后插头的话是 \(O(n^2m^22^m)\) 的。然而注意到每次只有一个地方变成障碍，那么正着 dp 一遍，倒着 dp 一遍，枚举合法状态（四个方向都没有插头）合并就行了。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=1000000007;
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
int n,m,f[18][18][1<<18],g[18][18][1<<18],ans[20][20],a[20][20];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]),a[i][j]^=1;
}
}
f[1][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int s=0;s<(1<<m+1);s++){
int l=(s>>j-1)&1,r=(s>>j)&1;
if(!a[i][j]){
if(!l&&!r)f[i][j][s]=add(f[i][j][s],f[i][j-1][s]);continue;
}
if(!l&&!r){
f[i][j][s]=add(f[i][j][s],f[i][j-1][s]);
if(a[i][j+1])f[i][j][s^(1<<j)]=add(f[i][j][s^(1<<j)],f[i][j-1][s]);
if(a[i+1][j])f[i][j][s^(1<<j-1)]=add(f[i][j][s^(1<<j-1)],f[i][j-1][s]);
}
if(!l&&r)f[i][j][s^(1<<j)]=add(f[i][j][s^(1<<j)],f[i][j-1][s]);
if(l&&!r)f[i][j][s^(1<<j-1)]=add(f[i][j][s^(1<<j-1)],f[i][j-1][s]);
}
}
if(i<n)for(int j=0;j<(1<<m+1);j++)f[i+1][0][j<<1]=f[i][m][j];
}
g[n][m+1][0]=1;
for(int i=n;i;i--){
for(int j=m;j;j--){
for(int s=0;s<(1<<m+1);s++){
int l=(s>>j-1)&1,r=(s>>j)&1;
if(!a[i][j]){
if(!l&&!r)g[i][j][s]=add(g[i][j][s],g[i][j+1][s]);continue;
}
if(!l&&!r){
g[i][j][s]=add(g[i][j][s],g[i][j+1][s]);
if(a[i][j-1])g[i][j][s^(1<<j-1)]=add(g[i][j][s^(1<<j-1)],g[i][j+1][s]);
if(a[i-1][j])g[i][j][s^(1<<j)]=add(g[i][j][s^(1<<j)],g[i][j+1][s]);
}
if(!l&&r)g[i][j][s^(1<<j)]=add(g[i][j][s^(1<<j)],g[i][j+1][s]);
if(l&&!r)g[i][j][s^(1<<j-1)]=add(g[i][j][s^(1<<j-1)],g[i][j+1][s]);
}
}
if(i>1)for(int j=0;j<(1<<m+1);j++)g[i-1][m+1][j>>1]=add(g[i-1][m+1][j>>1],g[i][1][j]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!a[i][j]){
printf("0 ");continue;
}
int s=((1<<m+1)-1)^(1<<j-1)^(1<<j);
for(int t=s;t;t=s&(t-1)){
int x=1ll*f[i][j-1][t]*g[i][j+1][t]%mod;
ans[i][j]=add(ans[i][j],x);
}
int x=1ll*f[i][j-1][0]*g[i][j+1][0]%mod;
ans[i][j]=add(ans[i][j],x);
printf("%d ",ans[i][j]);
}
printf("\n");
}
return 0;
}