插头DP & 轮廓线DP
柒葉灬
2019-08-11 15:08:38
# 插头DP 和 轮廓线DP
------
[专题 A - Mondriaan's Dream
](https://cn.vjudge.net/contest/317037#problem)（轮廓线DP）
**题意：** 给你一个$n\times m $ 的棋盘，用$1 \times 2$ 的块覆盖整个棋盘，问方案数？（$n,m \in [1,11] $）
**思路：** 数据范围很小，考虑用状压DP，单纯的状压DP的话转移起来有点困难，但若考虑单个位置的时候，情况变得简单起来：
1. 若该位置被覆盖，则不用管它
2. 若该位置没有被覆盖：(1)摆一个朝下的 (2)摆一个朝右的
普通的状压DP相当于还要枚举每个位置的状态，而轮廓线只要枚举一个就可以了。
具体细节看代码回忆。
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=15,maxm=1.8e6;
int n,m;
bool mark[maxn][maxn];
long long dp[2][1<<11];
int num(int x){return 1<<x-1;}
int getnum(int S,int x){return (S>>x-1)&1;}
int main(){
while(scanf("%d%d",&n,&m),n&&m){
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mark[i][j]=1;
memset(dp,0,sizeof(dp));
int cur=0;
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
for(int S=0;S<1<<m;S++){
int now=getnum(S,j),right=getnum(S,j+1);
long long val=dp[cur^1][S];
if(now){
dp[cur][S^num(j)]+=val;
}else {
if(mark[i+1][j])
dp[cur][S^num(j)]+=val;
if(mark[i][j+1]&&!right)
dp[cur][S^num(j+1)]+=val;
}
}
}
}
cout<<dp[cur][0]<<endl;
}
return 0;
}
```
-------
[专题
B - 方格取数(1)
](https://cn.vjudge.net/contest/317037#problem/B)
**题意：** ~~中文题面，自己看题~~
**思路：** 取一个数的时候只需要关心两个事：
(1)该位置能不能取
(2)这个位置取了会导致哪些位置的数不能取。
用 $1$ 表示这个位置可以取 $0$ 表示不能取，轮廓线DP即可。
------
[专题
C - Pebbles
](https://cn.vjudge.net/contest/317037#problem/C)
**题意：** 给一个 $n \times m$ 的矩阵，从中取出不相邻的若干个数，使得和最大。（$n,m \in [3,15]$）
（注意，这里相邻包括8个方向）
**思路：** 跟上一题的方格取数差不多，多加一进制表示这个位置以及下方的位置也不能取即可。
-----
## ------------- 分 ------------- 割 ------------- 线 -------------
### 很简单介绍
解决有关**连通性状压问题**一般考虑到插头
DP，
有关插头DP的文章：[插头DP](https://www.cnblogs.com/LadyLex/p/7326874.html)
注意：一定要区分**最小表示法** 和 **括号配对法** 不然会很乱，还有对于配对指的是两个插头**当前在一个连通块内**。
写多了题目形成自己的板子就行了。
------------------
[专题
D - Eat the Trees
](https://cn.vjudge.net/contest/317037#problem/D)
**题意：** 给 $n\times m$ 的矩阵，矩阵上有一些障碍，找**任意个**回路覆盖全部非障碍格子，求方案数。（$ n ,m \in [1,11]$）
**思路：** 由于不需要形成唯一回路，所以可以只记录有没有插头，至于左插头还是右插头可以不用管。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=15,maxm=1.8e6;
int n,m;
long long dp[maxn][1<<13];
bool mark[maxn][maxn];
int getnum(int S,int x){
return (S>>(x-1))&1;
}
int num(int x){
return 1<<x-1;
}
int main(){
for(int _,cas=(cin>>_,1);cas<=_;cas++){
scanf("%d%d",&n,&m);
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&mark[i][j]);
memset(dp,0,sizeof(dp));
dp[0][0]=1;
int cur=0;
for(int i=1;i<=n;i++){
cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
for(int S=0;S<1<<m;S++)
dp[cur][S<<1]=dp[cur^1][S];
for(int j=1;j<=m;j++){
cur^=1;memset(dp[cur],0,sizeof(dp[cur]));
for(int S=0;S<1<<m+1;S++){
int left=getnum(S,j),up=getnum(S,j+1);
long long val=dp[cur^1][S];
if(!mark[i][j]){
if(!left&&!up)dp[cur][S]+=val;
}else if(!left&&!up){
if(mark[i+1][j]&&mark[i][j+1])
dp[cur][S^num(j)^num(j+1)]+=val;
}else if(!left&&up){
if(mark[i+1][j])
dp[cur][S^num(j)^num(j+1)]+=val;
if(mark[i][j+1])
dp[cur][S]+=val;
}else if(left&&!up){
if(mark[i+1][j]);
dp[cur][S]+=val;
if(mark[i][j+1])
dp[cur][S^num(j)^num(j+1)]+=val;
}else if(left&&up){
dp[cur][S^num(j)^num(j+1)]+=val;
}
}
}
}
printf("Case %d: There are %lld ways to eat the trees.\n",cas,dp[cur][0]);
}
return 0;
}
```
---------
[
专题E - Formula 1
](https://cn.vjudge.net/contest/317037#problem/E)（插头DP）
**真·入门题**
**题意：** 给 $n\times m$ 的矩阵，矩阵上有一些障碍，找**一个**回路覆盖全部非障碍格子，求方案数。（$ n ,m \in [2,12]$）
**思路：** 这题不能像上一题一样只记录有没有插头了，因为如果形成多个回路就完了，需要记录该插头是左插头还是右插头。
（左插头的意思其实就是一个联通路径的左边插头）
在处理每一个格子的时候，相邻的只有左边和上面，
所以记左边插头状态为 $left$ ，上边的插头状态为 $up$
$0$ 表示没有插头，$1$ 表示是个左插头，$2$ 表示是个右插头
形成回路的点必须是最后一个，否则就可能出现多个回路。
每一对左插头右插头配对了，就说明多了一个回路，
而这题只能有一个，所以在最后的时候配对就行了，
**大力分类讨论：**
1. 如果这个点是障碍，那么必须$left==0\ and \ up==0$ 才能转移
2. 如果$ !left \ and \ !up$ 那么必须创造一个向下且向右的新插头（每个空格必须覆盖）
3. 如果$left \ and \ !up$，那么左插头要么延伸向下，要么向右，分两种情况讨论
4. 如果$!left \ and \ up$，同第 $3$ 种情况
5. 如果$left==1 \ and \ up==1$ 两个左插头碰在一起，那么连起来之后，对应的**两个右插头**则相应变为一对，其中**左边的变为左插头**。（模拟一下就想明白了）
6. 如果$left==2 \ and \ up==2 $ 两个右插头碰在一起，那么连起来之后，对应的**两个左插头**则相应变为一对，其中**右边的变为右插头**。（模拟一下就想明白了）
7. 如果$left==2 \ and \ up==1 $ 左边是右插头，右边是左插头，说明左右两个连通块连在了一起，模拟一下发现对应的两个插头都不需要改变。
8. 如果$left==1 \ and \ up==2 $ 左边左插头，右边右插头，说明要产生新的回路了，此时判断这个点是不是最后一个点，如果是则加入答案，否则就是不合法状态了。
-------
看似转移情况很多，~~实际上很多时候在复制粘贴~~ 自己写的时候只要自己模拟一下就行了，想通了话理解就能写出来了。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=15,maxm=1.8e6;
bool cur1;
int n,m,ex,ey;
long long ans;
char mp[maxn][maxn];
bool mark[maxn][maxn];
const int P=2333;
struct DP{
int tot,head[P],st[maxm],nxt[maxm];
long long sum[maxm];
void clear(){
memset(head,0,sizeof(head));tot=0;
}
int size(){return tot;}
void insert(int S,long long val){
int x=S%P;
for(int i=head[x];i;i=nxt[i]){
if(st[i]==S){
sum[i]+=val;
return;
}
}
st[++tot]=S;sum[tot]=val;
nxt[tot]=head[x];head[x]=tot;
}
}dp[2];
int getnum(int S,int x){
return (S>>((x-1)*2))&3;
}
int num(int x,int p){
return p<<(x-1<<1);
}
int main(){
while(cin>>n>>m){
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
for(int j=1;j<=m;j++){
if(mp[i][j]=='.'){
ex=i;ey=j;
mark[i][j]=1;
}
}
}
int cur=0;
ans=0;
dp[0].clear();
dp[0].insert(0,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=dp[cur].size();j++)
dp[cur].st[j]<<=2;
for(int j=1;j<=m;j++){
cur^=1;dp[cur].clear();
for(int k=1;k<=dp[cur^1].size();k++){
int S=dp[cur^1].st[k];
long long val=dp[cur^1].sum[k];
int left=getnum(S,j),up=getnum(S,j+1);
if(!mark[i][j]){
if(!left&&!up)
dp[cur].insert(S,val);
}else if(!left&&!up){
if(mark[i+1][j]&&mark[i][j+1])
dp[cur].insert(S+num(j,1)+num(j+1,2),val);
}else if(left&&!up){
if(mark[i+1][j])
dp[cur].insert(S,val);
if(mark[i][j+1])
dp[cur].insert(S^num(j,left)^num(j+1,left),val);
}else if(!left&&up){
if(mark[i][j+1])
dp[cur].insert(S,val);
if(mark[i+1][j])
dp[cur].insert(S^num(j+1,up)^num(j,up),val);
}else if(left==1&&up==1){
int cnt=1;
for(int l=j+2;l<=m+1;l++){
if(getnum(S,l)==1)cnt++;
else if(getnum(S,l)==2){
cnt--;
if(cnt==0){
S-=num(l,1);
break;
}
}
}
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==2&&up==1){
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==2&&up==2){
int cnt=1;
for(int l=j-1;l>=1;l--)
if(getnum(S,l)==1){
cnt--;
if(cnt==0){
S+=num(l,1);
break;
}
}else if(getnum(S,l)==2)cnt++;
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==1&&up==2){
if(i==ex&&j==ey)
ans+=val;
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
```
--------
[专题F](https://cn.vjudge.net/contest/317037#problem/F)
F题题意：一个N*M的图，其中X表示障碍，*表示空地，O表示必经点，求走一条回路经过所有必经点右多少种方案。
思路：对于空的格子可以有两种选择，加入插头或者不加入，终止状态则变成经过必经点后面的点。
------
[专题G](https://cn.vjudge.net/contest/317037#problem/G)
G题题意：一个n*m的房子，输入如样例，每个空格表示一个房间，数字表示把两个相邻的房间连起来所需的费用，#表示墙，求把所有房间连成一条回路的最小代价。
思路：在延伸出插头的时候加入权值防止重复或者漏加
------
[专题H](https://cn.vjudge.net/contest/317037#problem/H)
H题题意：一个n*m矩阵，求从左上角走到右下角（路径可以不经过所有点，但不能重复走一个点）的最小代价。
思路：(1)从外面加一条不存在的路线，使得形成回路 (2)引入独立插头进行DP
解法（1）更为方便
-------
[专题I](https://cn.vjudge.net/contest/317037#problem/I)
I题题意：一个n*m的图，#表示障碍，求从左下角走到右下角，经过所有非障碍点的路径方案数。
思路：与上题相似
------
[专题J](https://cn.vjudge.net/contest/317037#problem/J)
J题题意：一个n*m的图，0表示空地，1表示障碍，2/3表示2/3这条线的一个端点（2/3只会出现两次），求把2个2和2个3连起来且不相交的最短长度-2的值（可以看看题面的图）。如果无解输出0 。
思路：这题看似需要简单路径，其实并不，因为求得是路径长度和最短的，所以就算出现了无用的回路也无所谓，肯定会被最优解覆盖，所以插头就变成了 属于2还是属于3 两种插头。
-------
[专题K](https://cn.vjudge.net/contest/317037#problem/K)
K题题意：一个蜂巢，它有n行8列，编号见图，输入m个坐标表示障碍，求用多条回路铺满整个蜂巢有多少种方案。
思路：这题就是轮廓线多了几条边而已，分奇偶讨论不同轮廓线状态，代码有bug会极其难调
-------
[专题L](https://cn.vjudge.net/contest/317037#problem/L)
L题题意：一个n*m的图求从左上角走到左下角，经过所有点，有多少种方案，如果没有输出Impossible (2 <= N <= 7, 1 <= M <=10^9)
思路：m有点大，考虑矩阵快速幂，矩阵快速幂的时候不能形成回路，要特殊处理最后一排，因为 n<=7 爆搜出来的状态数不超过130，所以复杂度有保证。
--------
[专题M](https://cn.vjudge.net/contest/317037#problem/M)（独立插头的应用）
M题题意：一个n*m的矩阵，0表示障碍，其他数表示这个点的权值，求从任意起点出发，在任意终点结束（路径上的点不能重复走）的路径中，权值最大是多少。
思路：因为是一条路径，而且起点终点任意，所以需要引入独立插头，在每一个状态都不能同时存在大于2的独立插头，有的话不转移就行了。
独立插头的转移可以看插头DP开头放出来的博客，
或者说看代码（5K）理解。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=20;
int n,m;
int ans,mark[maxn][maxn];
const int P=23333,maxm=1e6;
struct DP{
int tot,head[P],st[maxm],nxt[maxm];
int mx[maxm];
void insert(int S,int val){
int x=S%P;
for(int i=head[x];i;i=nxt[i]){
if(st[i]==S){
mx[i]=max(mx[i],val);
return;
}
}
st[++tot]=S;mx[tot]=val;
nxt[tot]=head[x];head[x]=tot;
}
void clear(){
memset(head,0,sizeof(head));
tot=0;
}
int size(){
return tot;
}
}dp[2];
int getnum(int S,int x){
return (S>>(x-1<<1))&3;
}
int num(int x,int p){
return p<<(x-1<<1);
}
bool check(int S){
int cnt=0;
while(S){
if((S&3)==3)cnt++;
S>>=2;
}
return cnt<3;
}
int main(){
for(int _=(cin>>_,_);_--;){
scanf("%d%d",&n,&m);
ans=0;
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&mark[i][j]);
ans=max(ans,mark[i][j]);
}
int cur=0;
dp[0].clear();
dp[0].insert(0,0);
for(int i=1;i<=n;i++){
for(int k=1;k<=dp[cur].size();k++)
dp[cur].st[k]<<=2;
for(int j=1;j<=m;j++){
cur^=1;dp[cur].clear();
for(int k=1;k<=dp[cur^1].size();k++){
int S=dp[cur^1].st[k];
if(!check(S))continue;
int val=dp[cur^1].mx[k];
int left=getnum(S,j);
int up=getnum(S,j+1);
if(!mark[i][j]){
if(!left&&!up)dp[cur].insert(S,val);
continue;
}
val+=mark[i][j];
if(!left&&!up){
dp[cur].insert(S,val-mark[i][j]);
if(mark[i+1][j]&&mark[i][j+1])
dp[cur].insert(S^num(j,1)^num(j+1,2),val);
if(mark[i+1][j])
dp[cur].insert(S^num(j,3),val);
if(mark[i][j+1])
dp[cur].insert(S^num(j+1,3),val);
}else if(!left&&up){
if(mark[i+1][j]){
dp[cur].insert(S^num(j,up)^num(j+1,up),val);
}
if(mark[i][j+1])
dp[cur].insert(S,val);
if(up==1){
int cnt=1;
for(int l=j+2;;l++){
if(getnum(S,l)==1)cnt++;
else if(getnum(S,l)==2){
cnt--;
if(cnt==0){
S+=num(l,1);
break;
}
}
}
dp[cur].insert(S^num(j+1,up),val);
}else if(up==2){
int cnt=1;
for(int l=j-1;;l--){
if(getnum(S,l)==2)cnt++;
else if(getnum(S,l)==1){
cnt--;
if(cnt==0){
S+=num(l,2);
break;
}
}
}
dp[cur].insert(S^num(j+1,up),val);
}else {
S^=num(j+1,3);
if(S==0)ans=max(ans,val);
}
}else if(left&&!up){
if(mark[i+1][j])
dp[cur].insert(S,val);
if(mark[i][j+1])
dp[cur].insert(S^num(j,left)^num(j+1,left),val);
if(left==1){
int cnt=1;
for(int l=j+2;;l++){
if(getnum(S,l)==1)cnt++;
else if(getnum(S,l)==2){
cnt--;
if(cnt==0){
S+=num(l,1);
break;
}
}
}
dp[cur].insert(S^num(j,left),val);
}else if(left==2){
int cnt=1;
for(int l=j-1;;l--){
if(getnum(S,l)==2)cnt++;
else if(getnum(S,l)==1){
cnt--;
if(cnt==0){
S+=num(l,2);
break;
}
}
}
dp[cur].insert(S^num(j,left),val);
}else {
S^=num(j,3);
if(S==0)ans=max(ans,val);
}
}else if(left==1&&up==1){
int cnt=1;
for(int l=j+2;;l++){
if(getnum(S,l)==1)cnt++;
else if(getnum(S,l)==2){
cnt--;
if(cnt==0){
S-=num(l,1);
break;
}
}
}
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==2&&up==2){
int cnt=1;
for(int l=j-1;;l--){
if(getnum(S,l)==2)cnt++;
else if(getnum(S,l)==1){
cnt--;
if(cnt==0){
S+=num(l,1);
break;
}
}
}
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==2&&up==1){
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==1&&up==3||left==3&&up==1){
int cnt=1;
for(int l=j+2;;l++){
if(getnum(S,l)==1)cnt++;
else if(getnum(S,l)==2){
cnt--;
if(cnt==0){
S+=num(l,1);
break;
}
}
}
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==2&&up==3||left==3&&up==2){
int cnt=1;
for(int l=j-1;;l--){
if(getnum(S,l)==2)cnt++;
else if(getnum(S,l)==1){
cnt--;
if(cnt==0){
S+=num(l,2);
break;
}
}
}
dp[cur].insert(S^num(j,left)^num(j+1,up),val);
}else if(left==3&&up==3){
S^=num(j,left)^num(j+1,up);
if(S==0)ans=max(ans,val);
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
```
--------
[专题N](https://cn.vjudge.net/contest/317037#problem/N)
N题题意：一个n*m的矩阵，*表示障碍，每个点都必须在一个环上，且环之间不能嵌套（大环套小环），求恰好形成K个环的方案数。
思路：大环不能套小环是个很麻烦的事情，如何处理这个是本题的关键，有一个神奇的做法就是形成回路的时候左右配对的括号必须是偶数，一方面可以保证可以有方案使得没有环嵌套自己，也能让这个环没有嵌套别的环。
---------
当初为什么要学插头DP呢，就是为了解决这个题目↓
**「CTSC2010」产品销售** $\ \ \ \ \ \ \ \ \ \ $ ← 写个专题就是为了能A了这题！
↑ ↑ 对就是他，这题就算知道是插头DP也不一定搞得出来 ↑
是一个好题 ~~（毒瘤）~~
题目在203上的#262
-----------------
上面说过，一般的插头DP解决的是**连通性状压问题**
基础的就是回路了，拓展一下就是路径。
而这题不仅是路径还带有方向，所以需要改变一下插头的定义，
不能再是简单的左插头右插头了，
对于带有方向的路径问题：
1. 设插头0为没有插头
2. 设插头1为**向起点方向走的**
3. 设插头2为**向终点方向走的**
这样子可以保证既不产生回路（显然），
又能保证一个状态的表示
_（那之前有一个用独立插头的那题？能不能这么写呢？待补）_
这题需要知道上一次填的数是什么，下一步是变大还是变小，
前者压8位，后者压2位，用10位二进制表示一个状态。
---------------
这一压之后还有一个问题就是，
**怎么获知哪些数被取过了？**
先给出结论，对于一个状态，唯一对应一种取法，
具体证明，详见枚举结果：）
_↓ 模拟成果_
这里设3个插头分别为ABC，
默认若在同种插头状态下 权值A<权值B<权值C
一、有3个插头的情况
1. ABC都向小：不存在（只有一个起点）
2. AB向小，C向大：权值较大B肯定是从终点来的，A与C构成联通。——被取的区间为 $ [B,n*m] $ 和 $ [A,C] $。为什么C不与较大的B联通不用说了吧？
3. A向小，BC向大：权值较小B肯定是从起点来的，A与C构成联通。——被取的区间为 $[1,B]$和$[A,C]$。
3. ABC都向大：不存在（只有一个终点）
二、有2个插头的情况
1. AB都向小：不存在（只有一个起点）
2. A向小，B向大：被取的区间为$[A,B]$。
3. AB都向大：不存在（只有一个终点）
三、有1个插头的情况
1. A向小：被取的区间为$[A,n*m]$
2. A向大：被取的区间为$[1,A]$
四、有0个插头的情况
1. 初始状态和最终状态
----------------
**如果觉得上述方法过于麻烦，可以用bitset**
接着就是常规插头DP的分类讨论，
这里省略了01值相等是否的判断
设左边的权值为$leftnum$，状态为$leftst$
设上边的权值为$upnum$，状态为$upst$
一、$leftst==0\ \ \&\&\ \ upst==0 $
1. 插入$[2,n*m-1]$的值，
2. 插入$n*m$
3. 插入$1$，一定要注意起点在边界上
二、$leftst≠0\ \ \&\&\ \ upst==0 $
1. 插头延伸向下。
2. 插头延伸向右。
3. 注意延伸到头的情况，尤其是到了起点的情况。
三、$leftst==0\ \ \&\&\ \ upst≠0 $
1. 插头延伸向下。
2. 插头延伸向右。
3. 注意延伸到头的情况，尤其是到了起点的情况。
四、$leftst≠0\ \ \&\&\ \ upst≠0 $
1. 如果$leftst==upst$ ：不合法
2. 如果插头对应的后一个权值不一样：不合法
3. 合法就将两个插头接在一起。
（对于是否取过的判断在check的结构体内，对于插头的连接在main函数里面）
#### 最后贴上代码
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=55,P=11192869;
int n,m;
int A[4][maxn],B[maxn*3];
char str[maxn*3];
const int P2=233341,maxm=2e5;
struct DP{
int tot,head[P2],nxt[maxm],sum[maxm];
long long st[maxm];
int size(){
return tot;
}
void clear(){
memset(head,0,sizeof(head));
tot=0;
}
void insert(long long S,int val){
int x=S%P2;
for(int i=head[x];i;i=nxt[i]){
if(st[i]==S){
sum[i]=(sum[i]+val)%P;
return;
}
}
st[++tot]=S;sum[tot]=val;
nxt[tot]=head[x];head[x]=tot;
}
}dp[2];
int get(long long S,int x){
return (S>>(x-1)*10)&1023;
}
int getst(long long S,int x){//1表示向小 2表示向大
return get(S,x)&3;
}
int getnum(long long S,int x){
return get(S,x)>>2;
}
long long num(int val,int st,int p){
return 1LL*(val<<2|st)<<(p-1)*10;
}
struct Check{
int id;
struct node{
int op,x;
bool operator <(const node &_)const{
return op!=_.op?op<_.op:x<_.x;
}
}A[4];
void add(int S){
if(!S)return;
A[++id]=(node){S&3,S>>2};
}
void init(long long S){
id=0;
while(S){
add(S&1023);
S>>=10;
}
sort(A+1,A+1+id);
}
bool check(int x){
if(id==3){
if(A[2].op==1){
if(x>=A[2].x)return false;
if(x>=A[1].x&&x<=A[3].x)return false;
}else {
if(x<=A[2].x)return false;
if(x>=A[1].x&&x<=A[3].x)return false;
}
}if(id==2){
if(x>=A[1].x&&x<=A[2].x)return false;
}else if(id==1){
if(A[1].op==1){
if(x>=A[1].x)return false;
}else {
if(x<=A[1].x)return false;
}
}
return true;
}
}T;
int main(){
// freopen("trip.in","r",stdin);
// freopen("trip.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%s",str+1);
for(int j=1;j<=m;j++)
A[i][j]=(str[j]=='1');
}
scanf("%s",str+1);
for(int i=1;i<=n*m;i++)
B[i]=(str[i]=='1');
int cur=0;
dp[0].insert(0,1);
for(int j=1;j<=m;j++){
for(int k=1;k<=dp[cur].size();k++)
dp[cur].st[k]<<=10;
for(int i=1;i<=n;i++){
cur^=1;dp[cur].clear();
for(int k=1;k<=dp[cur^1].size();k++){
long long S=dp[cur^1].st[k];
int val=dp[cur^1].sum[k];
T.init(S);
int leftst=getst(S,i),leftnum=getnum(S,i);
int upst=getst(S,i+1),upnum=getnum(S,i+1);
if(!leftst&&!upst){
if(B[n*m]==A[i][j]&&T.check(n*m)){
if(i<n)dp[cur].insert(S^num(n*m,1,i+1),val);
if(j<m)dp[cur].insert(S^num(n*m,1,i),val);
}
if(B[1]==A[i][j]&&T.check(1)&&(i==1||i==n||j==1||j==m)){
if(i<n)dp[cur].insert(S^num(1,2,i+1),val);
if(j<m)dp[cur].insert(S^num(1,2,i),val);
}
if(i<n&&j<m){
for(int l=2;l<n*m;l++){
if(B[l]==A[i][j]&&T.check(l)){
dp[cur].insert(S^num(l,1,i)^num(l,2,i+1),val);
dp[cur].insert(S^num(l,2,i)^num(l,1,i+1),val);
}
}
}
}else if(!leftst&&upst){
int now=upnum+upst*2-3;
if(A[i][j]!=B[now]||!T.check(now))continue;
S^=num(upnum,upst,i+1);
if(now==n*m){
dp[cur].insert(S,val);
}else if(now==1){
if(i==1||j==1||i==n||j==m)dp[cur].insert(S,val);
}else {
if(i<n)dp[cur].insert(S^num(now,upst,i+1),val);
if(j<m)dp[cur].insert(S^num(now,upst,i),val);
}
}else if(leftst&&!upst){
int now=leftnum+leftst*2-3;
if(A[i][j]!=B[now]||!T.check(now))continue;
S^=num(leftnum,leftst,i);
if(now==n*m){
dp[cur].insert(S,val);
}else if(now==1){
if(i==1||j==1||i==n||j==m)dp[cur].insert(S,val);
}else {
if(i<n)dp[cur].insert(S^num(now,leftst,i+1),val);
if(j<m)dp[cur].insert(S^num(now,leftst,i),val);
}
}else if(leftst&&upst){
int now=leftnum+leftst*2-3;
if(upnum+upst*2-3!=now||upst==leftst||!T.check(now))continue;
if(A[i][j]!=B[now])continue;
dp[cur].insert(S^num(upnum,upst,i+1)^num(leftnum,leftst,i),val);
}
}
}
}
printf("%d\n",dp[cur].sum[1]);
return 0;
}
```