题解

题目类型：网格计数 / 状态压缩 DP / 插头 DP（括号匹配式）
取模：20110520

一、题意抽象

给定 (n\times m) 的网格，'_' 表示可用格，其他字符表示障碍。要求统计在可用格子上按局部合法规则连接/铺设的方案总数（障碍处不得放置、不得产生“悬空插头”），最终所有插头必须两两匹配闭合，答案对 20110520 取模。

本代码采用经典插头 DP（Plug DP）：在扫描到的“轮廓线”上，用两位编码表示每一列的插头状态，用“括号匹配”的方式维护连通关系，并枚举当前格的局部摆放/连接情况进行转移。到达末行末列时，只有全 0 状态（没有任何未配对插头）才可计入答案。

二、状态设计

• 轮廓线按“行优先”扫描，从左到右、从上到下。
• 为了压缩状态，将每一列上的插头用两位编码：
  • 0：无插头；
  • 1：左括号（相当于“开口”/一端）；
  • 2：右括号（相当于“闭口”/另一端）。
• 这样整行状态 s 是一个以 2 位为单位的“多位数”。
  辅助函数：
  • gw(s,i)：取出第 i 列（当前位置右侧一格）的 2-bit 值；
  • sw(s,i,w)：将第 i 列的 2-bit 置为 w 后返回新状态。

扫描到网格 ((i,j)) 时，轮廓线紧贴它的右侧和下侧，因此会同时读/写两处插头：
x = gw(s, j)（来自左侧的插头）与 y = gw(s, j+1)（来自上侧/右侧的插头）。

三、维度与稀疏优化

• 先将坐标旋转到 n ≥ m（若 n<m 则交换），降低状态宽度；
• 使用 __gnu_pbds::cc_hash_table 存储当前与下一层的 DP 映射 f[pre] / f[now]（稀疏状态）；
• 每处理一个格子就把 now 清空并与 pre 交换，保证内存与时间的可控。

四、转移规则（与代码一一对应）

设当前格为 a[i][j]（1 表示可用，0 表示障碍），取 x = gw(s,j)、y = gw(s,j+1)，以及当前状态权值 vl。对不同局部情形做如下转移（均对 MOD 取模）：

1) 障碍格（a[i][j]==0）

• 只能在既没有左插头、也没有上插头时保留原状：
  • 若 x==0 && y==0：add(f[now][s], vl)。

2) 可用格（a[i][j]==1）

情形 A：x==0 && y==0（当前无插头接入）

可在此格引入插头/配对，三种基本操作：

• 向“上/右”方向引一只插头（开一个括号）：
  • t = sw(s, j+1, 1)；add(f[now][t], vl)；
• 向“左/下”方向引一只插头（开一个括号）：
  • t = sw(s, j, 1)；add(f[now][t], vl)；
• 在此格成对出现（相当于两只插头彼此配对，不对外延伸）：
  • t = sw(sw(s, j, 2), j+1, 2)；add(f[now][t], vl)。

这三类操作覆盖了“在空白处新建局部连通”的三种最小形态：只在一侧伸出、或在格内闭合。

情形 B：x==0 && y!=0（只从“上/右”来了一只）

• 若 y==1（上侧是“开口”）：
  • 将其在此格“拐弯/延伸”：t = sw(s, j+1, 2)；add(...)；
  • 或将它与新开的另一只在此格配掉：t = sw(sw(s, j, 1), j+1, 0)；add(...)；
• 若 y==2（上侧是“闭口”）：
  • 与新开在 j 位的“闭口/开口”做相容处理：
  • t = sw(sw(s, j, 2), j+1, 0)；add(...)；
  • t = sw(sw(s, j, 0), j+1, 0)；add(...)。

情形 C：x!=0 && y==0（只从“左/下”来了一只）

• 与上面对称：
• 若 x==1：
  • t = sw(s, j, 2)；add(...)；
  • t = sw(sw(s, j, 0), j+1, 1)；add(...)；
• 若 x==2：
  • t = sw(sw(s, j, 0), j+1, 2)；add(...)；
  • t = sw(sw(s, j, 0), j+1, 0)；add(...)。

情形 D：x==1 && y==1

• 两个“开口”在此格直接匹配并消去：
  • t = sw(sw(s, j, 0), j+1, 0)；add(f[now][t], vl)。

（其它 x,y 的非零组合在这份模板里不会出现额外分支，已由上述对称/配平覆盖。）

五、换行与结算

• 每处理完一行的第 m 列后，还需做一次行转移：
  遍历 f[pre] 中的所有状态 s：
  • 若已到达最后一行（i==n），且 s==0（所有插头闭合），将其方案数累加进 ans；
  • 否则（未到最后一行），若虚拟列 gw(s, m+1)==0，将状态左移两位（对应“下移轮廓线”）：
    f[now][s<<2] += vl。

引入“虚拟列 m+1”是插头 DP 的常见技巧，保证每次取 gw(s,j+1) 不越界，同时行末做统一处理。

六、边界与实现细节

• 读入地图时，为了减少状态宽度，若 n < m 则转置读入并交换 n,m，始终保持 n ≥ m；
• 使用 cc_hash_table 存稀疏状态，避免 (O(3^m)) 的空转；
• 所有 add 操作均对 MOD=20110520 取模；
• 初始条件：f[0][0] = 1（空状态 1 种方案）。

七、复杂度

• 设有效列宽为 m，每格的有效状态数远小于理论上限，整体复杂度经验上约为
  [ O(n \cdot \text{states}(m)) ] 其中 states(m) 为稀疏状态规模（远小于 (3^m)），配合哈希表可通过 (n,m\le 100) 的数据规模。

八、代码（与题给一致）

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll=long long;
constexpr ll MOD=20110520;
int n,m;
ll ans;
cc_hash_table<int,int>a[101];
cc_hash_table<int,ll>f[2];

int gw(int s,int i){
	return s>>((i-1)<<1)&3;
}
int sw(int s,int i,int w){
	return s^(gw(s,i)<<((i-1)<<1))^(w<<((i-1)<<1));
}
void add(ll&x,ll y){
	x=(x+y>=MOD?x+y-MOD:x+y);
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=m;j++){
			if(n>=m) a[i][j]=(s[j-1]=='_'?1:0);
			else a[j][i]=(s[j-1]=='_'?1:0);
		}
	}
	if(n<m) swap(n,m);
	int pre=0,now=1;
	f[pre][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(auto p:f[pre]){
				int s=p.first;
				ll vl=p.second;
				int x=gw(s,j),y=gw(s,j+1);
				if(!a[i][j]){
					if(!x&&!y) add(f[now][s],vl);
				}else if(!x&&!y){
					int t=sw(s,j+1,1);
					add(f[now][t],vl);
					t=sw(s,j,1);
					add(f[now][t],vl);
					t=sw(sw(s,j,2),j+1,2);
					add(f[now][t],vl);
				}else if(!x){
					if(y==1){
						int t=sw(s,j+1,2);
						add(f[now][t],vl);
						t=sw(sw(s,j,1),j+1,0);
						add(f[now][t],vl);
					}else if(y==2){
						int t=sw(sw(s,j,2),j+1,0);
						add(f[now][t],vl);
						t=sw(sw(s,j,0),j+1,0);
						add(f[now][t],vl);
					}
				}else if(!y){
					if(x==1){
						int t=sw(s,j,2);
						add(f[now][t],vl);
						t=sw(sw(s,j,0),j+1,1);
						add(f[now][t],vl);
					}else if(x==2){
						int t=sw(sw(s,j,0),j+1,2);
						add(f[now][t],vl);
						t=sw(sw(s,j,0),j+1,0);
						add(f[now][t],vl);
					}
				}else if(x==1&&y==1){
					int t=sw(sw(s,j,0),j+1,0);
					add(f[now][t],vl);
				}
			}
			swap(pre,now);
			f[now].clear();
		}
		for(auto p:f[pre]){
			int s=p.first;
			ll vl=p.second;
			if(i==n&&!s) add(ans,vl);
			if(!gw(s,m+1)) add(f[now][s<<2],vl);
		}
		swap(pre,now);
		f[now].clear();
	}
	cout<<ans<<'\n';
    return 0;
}