Reincarnation

正因为梦易碎，才格外美好。

状态压缩 & 基于连通性的状压dp

发表于 更新于 分类于 ，
本文字数： 36k 阅读时长 ≈ 33 分钟

“在一切虚伪之下缔造而成的现实。”

有关状态压缩的扩展

码风申明

本人是无空格大括号换行人，变量名以明晰为原则。基于二进制位的特殊处理，所有数组从 开始计数。本人也习惯于从 开始，但是这样会对状态压缩的计算造成过多冗余。

状态表示优化

题目简介

题目名称：炮兵阵地
题目来源：

评测链接 ：https://loj.ac/p/10173
评测链接 ：https://www.luogu.com.cn/problem/P2704

形式化题意：给定一个大小为 的连通图，存在障碍。要求在其中摆上最多的棋子，使得任意一对棋子不会互相攻击，每一个棋子的攻击范围是以自己为中心的一个 的十字架。

数据范围：

为了表示方便，我们将 对调。

考虑到比较特殊的数据范围，以及这令人讨厌的计数问题，那就是状压 了，大概的思路也比较清晰，算是比较板的一道题。

令 表示第 行状态为 ，第 行状态为 ，第 行状态为 时，前 行可放炮兵的最大数量，对 各自进行枚举就可以得到答案，时间复杂度 ，容易发现是过不了的。

考虑状态压缩的常见优化——状态表示。

因为所有棋子都是等价的（指攻击方式），所以可以预处理出每一行能够放的状态，容易发现任意两个位置相隔距离必须 ，这样可以省去很多赘余状态。同样的道理，对于任意两个相邻行，其对第三行的限制也是固定的，所以我们可以通过枚举前两行来得到第三行的合法状态，预处理时间复杂度为 ，当然，我们已经预处理的前两行的合法状态，所以这个时间复杂度应当是理论复杂度。

此时我们就已经将时间复杂度优化到了可过的部分了，虽然理论值不变，但条件判定使得极其多的冗余状态被剔除，所以是可过的。但空间复杂度也需要优化，所以考虑滚动数组。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// ----- Eternally question-----
// Problem: P2704 [NOI2001] 炮兵阵地
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2704
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-23 15:16:56
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define popcount(x) __builtin_popcount(x)
const int MAXN=1e2+10,MAXM=11,MAXS=(1<<10)+10;
const int INF=0x3f3f3f3f;
int N,M,res;
bool Mp[MAXN][MAXM];
int Dp[2][MAXS][MAXS],Siz;
std::vector<int>ok,valid[MAXS][MAXS];
inline void init()
{
	for(int s=0;s<(1<<N);++s)
	{
		bool flag=0;
		for(int j=0;j<N-1&&(!flag);++j)
			if(s>>j&1) flag=(s>>(j+1)&1)|(s>>(j+2)&1);
		if(!flag) ok.push_back(s);
	}
	Siz=ok.size();
	for(int i=0;i<Siz;++i)
		for(int j=0;j<Siz;++j)
		{
			if(ok[i]&ok[j]) continue;
			for(int k=0;k<Siz;++k) if(!(ok[i]&ok[k])&&!(ok[j]&ok[k]))
				valid[i][j].push_back(k);
		}
}
inline bool check(int id,int state)
{
	for(int i=0;i<N;++i)
		if((state>>i&1)&&!Mp[id][i]) return 0;
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(M,N);
	for(int i=1;i<=M;++i)
		for(int j=0;j<N;++j)
		{
			char c=getchar();
			while(c!='P'&&c!='H') c=getchar();
			Mp[i][j]=(c=='P');
		}
	init();
	for(int s0=0;s0<Siz;++s0)
		for(int s1=0;s1<Siz;++s1)
			Dp[0][s0][s1]=-INF;
	Dp[0][0][0]=0;
	for(int i=1,op=1;i<=M;++i,op^=1)
	{
		for(int s0=0;s0<Siz;++s0)
			for(int s1=0;s1<Siz;++s1)
				Dp[op][s0][s1]=-INF;
		for(int s0=0;s0<Siz;++s0)
			for(int s1=0;s1<Siz;++s1)
			{
				if(Dp[op^1][s0][s1]==-INF) continue;
				for(int x:valid[s0][s1]) if(check(i,ok[x]))
					checkMax(Dp[op][x][s0],Dp[op^1][s0][s1]+popcount(ok[x]));
			}
	}
	for(int s0=0;s0<Siz;++s0)
		for(int s1=0;s1<Siz;++s1)
			checkMax(res,Dp[M&1][s0][s1]);
	write(res);
	return 0;
}
/*

*/

状态压缩的 lowbit 优化

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P2396

形式化题意：有 个数 与 个数 ，令 表示 的第 个排列， 表示排列 前 个数的和，问一共有多少个排列，使得 满足 ，对 取模。

数据范围：

状压 裸题，用 表示选数状态下的方案数，如果 ，则 不转移，否则转移。时间复杂度 ，然后你惊奇地发现居然过不了。

对于枚举状态 在这个过程中是必要的，所以我们要在那个 上优化。这个过程的实际意义是找到 中所有位置为 的位置，可以用 的 lowbit() 思想进行优化，可以把时间复杂度平衡到 内，所以总时间复杂度 ，可以通过。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// ----- Eternally question-----
// Problem: P2396 yyy loves Maths VII
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2396
// Memory Limit: 222 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-23 16:09:07
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=25,MAXS=1<<24|10;
const int Mod=1e9+7;
int N,M,Dist[MAXS],Dp[MAXS],b[2];
std::map<int,bool>Mp;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=0;i<N;++i) read(Dist[1<<i]);
	read(M);
	for(int i=0;i<M;++i) read(b[i]);
	Dp[0]=1;
	for(int s=1,x;s<(1<<N);++s)
	{
		int s0=s;x=s&(-s);
		Dist[s]=Dist[x]+Dist[s^x];
		if(Dist[s]==b[0]||Dist[s]==b[1]) continue;
		while(s0)
		{
			Dp[s]=(Dp[s]+Dp[s^x])%Mod;
			s0^=x;x=s0&(-s0);
		}
	}
	write(Dp[(1<<N)-1]);
	return 0;
}
/*

*/

状态压缩与概率

题目简介

题目名称：奖励关
题目来源：四川省选 （具体不详）

评测链接：https://www.luogu.com.cn/problem/P2473

形式化题意：共有 个物品，每一个物品有一个价值 和一个依赖集合 ，即只有 中的所有元素都已经被选过了 才能被选。一共有 轮，每一轮会以 的几率给出任意一个物品，你可以选或者不选，求最优抉择下的平均价值。

数据范围：

主体是概率 ，但我们需要借用状态压缩的思想。

记 表示 轮中，被选择过的状态为 ，然后枚举 ，判断第 个是否能够被选，然后就可以进行较优判断，因为我们是逆推转移，所以直接取 max 即可。

转移方程如下：

时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// ----- Eternally question-----
// Problem: P2473 [SCOI2008] 奖励关
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2473
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-23 16:43:31
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXK=1e2+10,MAXN=16,MAXS=1<<15|10;
int K,N,p[MAXN],frt[MAXN];
double Dp[MAXK][MAXS];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(K,N);
	for(int i=0,x;i<N;++i)
	{
		read(p[i],x);
		while(x)
		{ frt[i]|=1<<(x-1);read(x); }
	}
	for(int day=K;day;--day)
		for(int s=0;s<(1<<N);++s)
		{
			for(int i=0;i<N;++i)
			{
				if((s&frt[i])==frt[i]) Dp[day][s]+=std::max(Dp[day+1][s],Dp[day+1][s|(1<<i)]+p[i]);
				else Dp[day][s]+=Dp[day+1][s];
			}
			Dp[day][s]/=(double)N;
		}
	printf("%.6lf",Dp[1][0]);
	return 0;
}
/*

*/

状态压缩与位运算

题目简介

题目名称：学校食堂
题目来源：山东省选

评测链接：https://www.luogu.com.cn/problem/P2157

形式化题意：每一个人有 个权值 ，你需要构造一个 的排列 ，使得对于任意的 中 的个数不能超过 个，且 ，这个排列的权值和为 ，求最小的 。多测。

数据范围：

首先可以将 优化成 ，然后考虑到 足够小，我们就可以进行状态压缩。

令 表示当前 的人都已经打到饭，且 是否打过饭的状态为 ，上一个打饭的人编号为 ，显然地， 的范围是 ，这样的话，就按照常规方法转移就是了。

注意到可以优化 ，大家应该都知道吧……

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// ----- Eternally question-----
// Problem: P2157 [SDOI2009] 学校食堂
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2157
// Memory Limit: 125 MB
// Time Limit: 800000 ms
// Written by: Eternity
// Time: 2023-03-10 19:59:34
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e3+10,MAXK=20,MAXS=1<<8|10;
const int INF=0x3f3f3f3f;
const int K=8;
int Test,N,T[MAXN],B[MAXN];
int Dp[MAXN][MAXS][MAXK];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N);
		for(int i=1;i<=N;++i) read(T[i],B[i]);
		std::memset(Dp,0x3f,sizeof(Dp));
		Dp[1][0][7]=0;
		for(int i=1;i<=N;++i)
			for(int s=0;s<(1<<8);++s)
				for(int k=-8;k<=7;++k)
				{
					if(Dp[i][s][k+K]==INF) continue;
					if(s&1) checkMin(Dp[i+1][s>>1][k+K-1],Dp[i][s][k+K]);
					else
					{
						int res=INF;
						for(int j=0;j<=7;++j) if(!(s>>j&1))
						{
							if(i+j>res) break;
							checkMin(res,i+j+B[i+j]);
							checkMin(Dp[i][s|(1<<j)][j+K],Dp[i][s][k+K]+(i+k?(T[i+k]^T[i+j]):0));
						}
					}
				}
		int ans=INF;
		for(int k=0;k<=8;++k) checkMin(ans,Dp[N+1][0][k]);
		write(ans,'\n');
	}
	return 0;
}
/*

*/

基于连通性的状态压缩

容易发现，状态压缩是一个针对一维状态进行扩展的算法，而我们使用状压 时却往往解决的是二维网格图类型的问题，在对列进行较大限制时会造成空间与时间上的冗余，从而使得有些题目在没有其它方法的时候并没有办法通过维护基本状态通过。

这个时候，我们强大的 通过总结归纳与创新研发而出的基于连通性状态压缩的动态规划，俗称插头 。

观前提醒

此内容并不属于 大纲范围，且整体观感较难（在洛谷中评级为 ），对于 选手而言不是必要掌握内容，请读者结合自身需求进行学习。

轮廓线式动态规划

对于原本的状态压缩，我们会将整个网格图“分层”，从上一层向下一层进行状态转移，这样下来的话，一共会经历 层转移，每一层都会进行 的遍历，如果还要枚举上一层的状态则会让时间劣到 ，这是一个不太优秀的结果。

而轮廓线 可以使这样的算法优化到 。

对于一个二维问题而言，我们从上往下转移，则对于中间某一刻而言，我们可以用一条穿过了网格边界的线将整个网格图划分为未转移和已转移两部分，如下图所示：

image

图片来自

图中的那一条红线就是我们所说的轮廓线。

此时，我们的状态依然是其列数即 ，但这个 表示的坐标分别是 ，也就是轮廓线之上的 个点，然后我们一个点一个点地进行转移。

骨牌问题

题目简介

题目名称：蒙德里安的梦想
题目来源：不详
评测链接 ：https://www.acwing.com/problem/content/293
评测链接 ：https://vjudge.net/problem/HDU-1400

形式化题意：用 的小型长方形铺满 的空间，求方案总数。

数据范围：

这是一个状压 的经典问题，也是一道较为模板的入门练习题，但现在我们从轮廓线的角度来对其进行解决。

设定 表示当前转移至 ，即 都已经被转移过了，且轮廓线状态为 的方案总数。

对于当前结点 ，其可能成为：

  • 竖放骨牌的上半部分，此时该格点无法对轮廓线之上的任意结点造成影响。
  • 竖放骨牌的下半部分，则应当转移的部分应与 配对。
  • 横放骨牌的左半部分，此时该格点无法对轮廓线之上的任意结点造成影响。
  • 横放骨牌的右半部分，则应当转移的部分应与 配对。

我们令状态中的 表示当前结点属于一个竖放骨牌的上半部分，在此基础上进行转移。若 时，我们应从 进行转移；否则，应从 和 进行转移。

而对于 转移时，需要继承所有的 状态以保证轮廓线不会进行突变，即轮廓线的完整性。

这样的时间复杂度是 ，足以通过加强版。为了配合坐标所以下标从 开始了，所以代码看起来有点冗杂。

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/UVA11270

形式化题意：用 的小型长方形铺满 的空间，求方案总数。

数据范围：

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// ----- Eternally question-----
// Problem: Tiling Dominoes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA11270
// Memory Limit: 0 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-23 20:52:40
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=11,MAXM=1e2+10,MAXS=1<<10|10;
int N,M;
ll Dp[MAXM][MAXN][MAXS];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	while(~scanf("%d%d",&N,&M))
	{
		if(N<M) std::swap(N,M);
		Dp[0][M][0]=1;
		for(int i=1;i<=N;++i)
		{
			for(int k=0;k<(1<<M);++k) Dp[i][0][k]=Dp[i-1][M][k];
			for(int j=1;j<=M;++j)
				for(int k=0;k<(1<<M);++k)
				{
					Dp[i][j][k]=Dp[i][j-1][k^(1<<(j-1))];
					if(j>1&&!(k&(3<<(j-2)))) Dp[i][j][k]+=Dp[i][j-2][k];
				}
		}
		write(Dp[N][M][0],'\n');
	}
	return 0;
}
/*

*/

插头动态规划

所谓插头是一种基于轮廓线的概念。我们在网格图中添加连通的概念，注意此连通是网格图之外的连通，即 不一定和其四连通结点在此意义下连通。插头是轮廓线上存在于某一段长度为 的边上的定义，如果 与 连通，且 为轮廓线，则称该段存在插头， 且是水平插头。

显然发现，对于一个 的网格图，至多存在 个竖直插头和 个水平插头。在插头 中，我们的状态即是压缩这 个插头。

题目简介

题目名称：

题目来源：

评测链接 ：https://www.luogu.com.cn/problem/P5074
评测链接 ：https://vjudge.net/problem/HDU-1693

形式化题意：用若干条回路覆盖 的网格图，有些位置存在障碍物，求方案数。

数据范围：

从插头方面考虑，当一种方案合法时，除了障碍物格子之外，所有格子都有且仅有 个插头，这样考虑会简单很多：

image

图片来自：

我们的转移分为下列 种情况：

  • 从 均不存在插头转移到 均存在插头。
  • 从 均存在插头转移到 均不存在插头。
  • 从 其一存在插头转移到 其一存在插头。

由于水平插头一定与其中 个竖直插头相连，所以我们可以连通式转移，即一次性转移 个插头的状态。时间复杂度分析与上一道题一致。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// ----- Eternally question-----
// Problem: P5074 Eat the Trees
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5074
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-23 21:38:20
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=13,MAXS=1<<12|10;
int Test,N,M,Mp[MAXN][MAXN];
ll Dp[MAXN][MAXN][MAXS];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N,M);
		for(int i=1;i<=N;++i)
			for(int j=1;j<=M;++j)
				read(Mp[i][j]);
		Dp[0][M][0]=1;
		for(int i=1;i<=N;++i)
		{
			for(int s=0;s<(1<<M);++s) Dp[i][0][s<<1]=Dp[i-1][M][s];
			for(int j=1;j<=M;++j)
				for(int s=0;s<(1<<(M+1));++s)
				{
					if(!Mp[i][j])
					{
						if(!(s>>(j-1)&3)) Dp[i][j][s]=Dp[i][j-1][s];
						else Dp[i][j][s]=0;
					}
					else
					{
						if(!!(s>>(j-1)&1)==!!(s>>j&1)) Dp[i][j][s]=Dp[i][j-1][s^(3<<(j-1))];
						else Dp[i][j][s]=Dp[i][j-1][s^(3<<(j-1))]+Dp[i][j-1][s];
					}
				}
		}
		write(Dp[N][M][0],'\n');
	}
	return 0;
}
/*

*/

完全连通性插头

题目简介

题目名称：插头

题目来源：

评测链接：https://www.luogu.com.cn/problem/P5056

形式化题意：给出 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法。

数据范围：

我们发现，虽然都是求闭合回路，但对于这道题而言，必须是一个完全连通的闭合回路，意味着在 个插头之外，我们需要一个更为强有力的条件为我们服务。

根据 的研究，对于此类完全连通性棋盘的问题，有一个非常重要的性质：

image

图片来自

对于 个水平插头，任意 个 ，若 连通，则 一定不连通。

这个证明其实是显然地，对于已转移部分，如果 和 连通，则其一定存在交点，那交点所在的格子就一定多余 个插头，从而背离性质。也正是如此，衍生而出了 种不同的插头 法。

最小表示法

对于所有相连的插头进行由小到大赋值，每一个连通块为一个编号，采用 进制存储。此表示记录的是轮廓线上的插头的位置。

括号表示法

我们做过很多有关括号匹配的问题，例如 (((..(.))...)..) 就是一个合法序列。用一对 表示相连的 个插头，与最小表示法中同一编号的插头意义一致。使用 进制压缩。

哈希加速

容易发现，在每一次转移间会存在许许多多未曾被使用过的插头，他们的数值为 ，这会大大增加我们状态压缩的枚举量，客观来讲，在这类题中，合法状态是稀疏的。所以我们需要一个 表来记录合法状态，甚至还可以将转移封装进去。可以选择 std::unordered_map 来代替手写哈希。

转移

令现在我们所转移的格点为 ，就会存在以下几种情况，我们设 分别表示第 个插头的状态：

  1. 为障碍，且 ：

    那就可以直接进行转移。
  2. 可以走，且 ：

    也就是我们现在转移的这个格点的左上并没有插头，这是一个全新的结点，我们就需要重新开一条路径，这里必须保证 都不是障碍才行。在括号表示法中，我们相当于在 个 . 中添加了一对相邻的 。
  3. 可走，且 ：

    那么 和 必须相连，我们就需要在 和 中选择一个进行转移，当然，都可以的话就分别转移。
  4. 可走，且 ，我们需要进一步分类讨论
    • 若 ：也就是存在 (..(..).) 的情况，我们现在要使其成为 ......(.) 的情况，删除左括号，并使 个右括号匹配。
    • 若 ：与上一种情况类似，删除 个右括号，并使左括号匹配。
    • 若 ：变 (...)....(.) 为 (..........)，合并 对括号。
    • 若 ：这是回路的闭合部分，也就是一个连通块中的最后一个结点和最后 个插头，此时无需转移，直接更新答案。

一共有 个讨论，避免冗杂的代码，我们对其中的操作进行函数式实现。

代码实现

变量申明
 
1
2
3
4
5
6
7
const int MAXN=15,MAXS=1<<12|10,MAXH=1e6+10;	//最大图，最大状压，最大哈希
const int Mod=999973;				//合适的哈希模数
int N,M,EndX,EndY;				//图大小，终结点
char Mp[MAXN][MAXN];				//图
int Head[MAXH],Nxt[MAXH],Dist[2][MAXH];		//哈希链表头指针，链接，距头指针长度
int Pos,Pre,Cnt[MAXH];				//滚动数组（0/1），哈希长度
ll ans,Val[2][MAXH],Pow4[MAXN];			//答案，对应Dist的贡献值，预处理4的阶乘
更新函数
 
1
2
3
4
5
6
7
8
9
10
11
12
inline void upDate(int bit,ll v)
{
	int bt1=bit%Mod+1;
	for(int x=Head[bt1];x;x=Nxt[x])
		if(Dist[Pos][x]==bit) return Val[Pos][x]+=v,void();
		//如果这个状态在哈希中已经存在过了，就叠加贡献
		//否则新建结点记录状态和贡献
	++Cnt[Pos];
	Nxt[Cnt[Pos]]=Head[bt1];Head[bt1]=Cnt[Pos];
	Dist[Pos][Cnt[Pos]]=bit,Val[Pos][Cnt[Pos]]=v;
	return ;
}
动态规划过程
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
inline void solve()
{
	Pos=0,Pre=1;			//滚动数组
	upDate(0,1);
	for(int i=1;i<=N;++i)
	{
		for(int k=1;k<=Cnt[Pos];++k) Dist[Pos][k]<<=2;
		for(int j=1;j<=M;++j)
		{
			std::memset(Head,0,sizeof(Head));
			std::swap(Pos,Pre);Cnt[Pos]=0;
			for(int k=1;k<=Cnt[Pre];++k)
			{
				int bit=Dist[Pre][k];ll v=Val[Pre][k];
				int p=(bit>>((j-1)<<1))&3,q=(bit>>(j<<1))&3;
				//待修改状态，贡献，左上插头状态，右下插头状态
				if(Mp[i][j]=='*') ((!p)&&(!q))&&(upDate(bit,v),1);
				else if((!p)&&(!q)) (Mp[i+1][j]=='.'&&Mp[i][j+1]=='.')&&(upDate(bit+Pow4[j-1]+(Pow4[j]<<1),v),1);
				else if((!p)&&q)
				{
					if(Mp[i+1][j]=='.') upDate(bit-Pow4[j]*q+Pow4[j-1]*q,v);
					if(Mp[i][j+1]=='.') upDate(bit,v);
				}
				else if(p&&(!q))
				{
					if(Mp[i+1][j]=='.') upDate(bit,v);
					if(Mp[i][j+1]=='.') upDate(bit-Pow4[j-1]*p+Pow4[j]*p,v);
				}
				else if(p&&q)
				{
					if(p==1&&q==1)
					{
						int l=1;
						for(int s=j+1;s<=M;++s)
						{
							if(((bit>>(s<<1))&3)==1) ++l;
							if(((bit>>(s<<1))&3)==2) --l;
							if(!l){ upDate(bit-Pow4[j-1]-Pow4[j]-Pow4[s],v);break; }
						}
					}
					else if(p==2&&q==2)
					{
						int l=1;
						for(int s=j-2;~s;--s)
						{
							if(((bit>>(s<<1))&3)==1) --l;
							if(((bit>>(s<<1))&3)==2) ++l;
							if(!l){ upDate(bit-(Pow4[j-1]<<1)-(Pow4[j]<<1)+Pow4[s],v);break; }
						}
					}
					else if(p==2&&q==1) upDate(bit-(Pow4[j-1]<<1)-Pow4[j],v);
					else (i==EndX&&j==EndY)&&(ans+=v);
					//所述7种情况的分讨
				}
			}
		}
	}
}
预处理部分
 
1
2
3
4
5
6
7
8
9
10
read(N,M);
for(int i=1;i<=N;++i) scanf("%s",Mp[i]+1);
for(int i=1;i<=N;++i)
	for(int j=1;j<=M;++j)
		if(Mp[i][j]=='.') EndX=i,EndY=j;
Pow4[0]=1;
for(int i=1;i<=M;++i) Pow4[i]=Pow4[i-1]<<2;
solve();
write(ans);
return 0;
AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// ----- Eternally question-----
// Problem: P5056 【模板】插头 dp
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5056
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-26 16:11:31
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=15,MAXS=1<<12|10,MAXH=1e6+10;
const int Mod=999973;
int N,M,EndX,EndY;
char Mp[MAXN][MAXN];
int Head[MAXH],Nxt[MAXH],Dist[2][MAXH];
int Pos,Pre,Cnt[MAXH];
ll ans,Val[2][MAXH],Pow4[MAXN];
inline void upDate(int bit,ll v)
{
	int bt1=bit%Mod+1;
	for(int x=Head[bt1];x;x=Nxt[x])
		if(Dist[Pos][x]==bit) return Val[Pos][x]+=v,void();
	++Cnt[Pos];
	Nxt[Cnt[Pos]]=Head[bt1];Head[bt1]=Cnt[Pos];
	Dist[Pos][Cnt[Pos]]=bit,Val[Pos][Cnt[Pos]]=v;
	return ;
}
inline void solve()
{
	Pos=0,Pre=1;			//滚动数组
	upDate(0,1);
	for(int i=1;i<=N;++i)
	{
		for(int k=1;k<=Cnt[Pos];++k) Dist[Pos][k]<<=2;
		for(int j=1;j<=M;++j)
		{
			std::memset(Head,0,sizeof(Head));
			std::swap(Pos,Pre);Cnt[Pos]=0;
			for(int k=1;k<=Cnt[Pre];++k)
			{
				int bit=Dist[Pre][k];ll v=Val[Pre][k];
				int p=(bit>>((j-1)<<1))&3,q=(bit>>(j<<1))&3;
				if(Mp[i][j]=='*') ((!p)&&(!q))&&(upDate(bit,v),1);
				else if((!p)&&(!q)) (Mp[i+1][j]=='.'&&Mp[i][j+1]=='.')&&(upDate(bit+Pow4[j-1]+(Pow4[j]<<1),v),1);
				else if((!p)&&q)
				{
					if(Mp[i+1][j]=='.') upDate(bit-Pow4[j]*q+Pow4[j-1]*q,v);
					if(Mp[i][j+1]=='.') upDate(bit,v);
				}
				else if(p&&(!q))
				{
					if(Mp[i+1][j]=='.') upDate(bit,v);
					if(Mp[i][j+1]=='.') upDate(bit-Pow4[j-1]*p+Pow4[j]*p,v);
				}
				else if(p&&q)
				{
					if(p==1&&q==1)
					{
						int l=1;
						for(int s=j+1;s<=M;++s)
						{
							if(((bit>>(s<<1))&3)==1) ++l;
							if(((bit>>(s<<1))&3)==2) --l;
							if(!l){ upDate(bit-Pow4[j-1]-Pow4[j]-Pow4[s],v);break; }
						}
					}
					else if(p==2&&q==2)
					{
						int l=1;
						for(int s=j-2;~s;--s)
						{
							if(((bit>>(s<<1))&3)==1) --l;
							if(((bit>>(s<<1))&3)==2) ++l;
							if(!l){ upDate(bit-(Pow4[j-1]<<1)-(Pow4[j]<<1)+Pow4[s],v);break; }
						}
					}
					else if(p==2&&q==1) upDate(bit-(Pow4[j-1]<<1)-Pow4[j],v);
					else (i==EndX&&j==EndY)&&(ans+=v);
				}
			}
		}
	}
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) scanf("%s",Mp[i]+1);
	for(int i=1;i<=N;++i)
		for(int j=1;j<=M;++j)
			if(Mp[i][j]=='.') EndX=i,EndY=j;
	Pow4[0]=1;
	for(int i=1;i<=M;++i) Pow4[i]=Pow4[i-1]<<2;
	solve();
	write(ans);
	return 0;
}
/*

*/

插头动态规划例题

模板试手

题目简介

题目名称：邮递员
题目来源：湖南省选 （具体不详）

评测链接：https://www.luogu.com.cn/problem/P2289

形式化题意：给定一个 的网格图，要求用一条有向完全连通闭合路径覆盖整张图，请问一共有多少种覆盖方法。

数据范围：

这道题甚至比模板要简单一点，因为不存在障碍，所以所有的插头状态都是合法的，就不需要哈希来进行存储，将 EndX,EndY 直接赋为 n,m 即可。注意 数据范围不同，我们应该选择范围较小的那一个进行压缩，否则会导致时间超限。而极限数据下的答案会爆 long long，所以需要 __int128_t 或者高精度（那个年代 __int128_t 还没有研发出来吧……），最后特判 的情况，虽然我觉得无解但答案给的 ，那就特判吧。因为是有向的所以答案 即可。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// ----- Eternally question-----
// Problem: P2289 [HNOI2004]邮递员
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2289
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-02-27 14:35:37
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using int128=__int128_t;
const int MAXN=22,MAXS=1<<11|10,MAXH=1e6+10;
const int Mod=999973;
int N,M,EndX,EndY;
char Mp[MAXN][MAXN];
int Head[MAXH],Nxt[MAXH],Dist[2][MAXH];
int Pos,Pre,Cnt[MAXH];
int128 ans,Val[2][MAXH],Pow4[MAXN];
inline void upDate(int bit,int128 v)
{
	int bt1=bit%Mod+1;
	for(int x=Head[bt1];x;x=Nxt[x])
		if(Dist[Pos][x]==bit) return Val[Pos][x]+=v,void();
	++Cnt[Pos];
	Nxt[Cnt[Pos]]=Head[bt1];Head[bt1]=Cnt[Pos];
	Dist[Pos][Cnt[Pos]]=bit,Val[Pos][Cnt[Pos]]=v;
	return ;
}
inline void solve()
{
	Pos=0,Pre=1;
	upDate(0,1);
	for(int i=1;i<=N;++i)
	{
		for(int k=1;k<=Cnt[Pos];++k) Dist[Pos][k]<<=2;
		for(int j=1;j<=M;++j)
		{
			std::memset(Head,0,sizeof(Head));
			std::swap(Pos,Pre);Cnt[Pos]=0;
			for(int k=1;k<=Cnt[Pre];++k)
			{
				int bit=Dist[Pre][k];int128 v=Val[Pre][k];
				int p=(bit>>((j-1)<<1))&3,q=(bit>>(j<<1))&3;
				if(Mp[i][j]=='*') ((!p)&&(!q))&&(upDate(bit,v),1);
				else if((!p)&&(!q)) (Mp[i+1][j]=='.'&&Mp[i][j+1]=='.')&&(upDate(bit+Pow4[j-1]+(Pow4[j]<<1),v),1);
				else if((!p)&&q)
				{
					if(Mp[i+1][j]=='.') upDate(bit-Pow4[j]*q+Pow4[j-1]*q,v);
					if(Mp[i][j+1]=='.') upDate(bit,v);
				}
				else if(p&&(!q))
				{
					if(Mp[i+1][j]=='.') upDate(bit,v);
					if(Mp[i][j+1]=='.') upDate(bit-Pow4[j-1]*p+Pow4[j]*p,v);
				}
				else if(p&&q)
				{
					if(p==1&&q==1)
					{
						int l=1;
						for(int s=j+1;s<=M;++s)
						{
							if(((bit>>(s<<1))&3)==1) ++l;
							if(((bit>>(s<<1))&3)==2) --l;
							if(!l){ upDate(bit-Pow4[j-1]-Pow4[j]-Pow4[s],v);break; }
						}
					}
					else if(p==2&&q==2)
					{
						int l=1;
						for(int s=j-2;~s;--s)
						{
							if(((bit>>(s<<1))&3)==1) --l;
							if(((bit>>(s<<1))&3)==2) ++l;
							if(!l){ upDate(bit-(Pow4[j-1]<<1)-(Pow4[j]<<1)+Pow4[s],v);break; }
						}
					}
					else if(p==2&&q==1) upDate(bit-(Pow4[j-1]<<1)-Pow4[j],v);
					else (i==EndX&&j==EndY)&&(ans+=v);
				}
			}
		}
	}
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(M,N);
	if(N<M) std::swap(N,M);
	if(N==1||M==1) return puts("1"),0;
	EndX=N,EndY=M;
	for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) Mp[i][j]='.';
	Pow4[0]=1;
	for(int i=1;i<=M;++i) Pow4[i]=Pow4[i-1]<<2;
	solve();
	write(ans<<1);
	return 0;
}
/*

*/

多测优化

题目简介

题目名称：白金元首与莫斯科
题目来源： 月赛

评测链接 ：https://www.luogu.com.cn/problem/P4262
评测链接 ：https://loj.ac/p/6301

形式化题意：给定一个 的网格图，其中有一些障碍。对于每一个点，询问当其成为障碍时，用 的长方形铺设网格图（无需铺满）的方案总数。当该点为障碍时答案为 。

数据范围：

时空限制：

容易发现，如果这个网格图已经固定了，那我们就可以用插头很好地做这道题。对于每一个非障碍格点，要么存在一个插头（与四连通的某个格点组成 的长方形），要么不存在插头（没有），然后逐个转移即可，时间复杂度 。

但显然，如果我们整 次插头是肯定不行的。所以要考虑一些优化。

如果一个格点存在障碍，那这个格点就不能有任意插头，从而，其四连通格点也不能存在任何与之相连的插头。这个时候，我们可以考虑反向做一次插头 ，使得有 条轮廓线将当前点给“包”住，我们记为 ，容易发现，如果某个结点为障碍，我们的答案就应该是 ，其中 是强制 不连通下的所有合法情况的子集。

这样的话，我们的时间复杂度就能优化到 了。虽然这道题有些卡常，但似乎连哈希加速都不需要。值得注意的是，边界应当被视为障碍。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// ----- Eternally question-----
// Problem: P4262 [Code+#3]白金元首与莫斯科
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4262
// Memory Limit: 1000 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-03-03 20:10:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=19,MAXS=1<<18|10;
int Mod=1e9+7;
int N,M,S,Mp[MAXN][MAXN];
int Dp[2][MAXN][MAXN][MAXS];
int ans[MAXN][MAXN];
int St[2],Ed[2],Nxt[2],Bg[2],Fl[2];
inline void add(int &a,int b)
{ a=a+b>Mod?a+b-Mod:a+b; }
inline void solve(int op)
{
	for(int i=St[op];i!=Ed[op];i+=Nxt[op])
	{
		if(!op) for(int s=0;s<=S;++s) add(Dp[0][i][0][s<<1],Dp[0][i-1][M][s]);
		else for(int s=0;s<=S;++s) add(Dp[1][i][M+1][s>>1],Dp[1][i+1][1][s]);
		for(int j=Bg[op];j!=Fl[op];j+=Nxt[op])
			for(int s=0;s<=S;++s)
			{
				int val=op?Dp[1][i][j+1][s]:Dp[0][i][j-1][s];
				if(!val) continue;
				int pl1=(s>>(j-1))&1,pl2=(s>>j)&1;
				if(!Mp[i][j]) (!pl1&&!pl2)&&(add(Dp[op][i][j][s],val),1);
				else if(!pl1&&!pl2)
				{
					add(Dp[op][i][j][s],val);
					if(!op)
					{
						if(Mp[i+1][j]) add(Dp[0][i][j][s^(1<<(j-1))],val);
						if(Mp[i][j+1]) add(Dp[0][i][j][s^(1<<j)],val);
					}
					else
					{
						if(Mp[i-1][j]) add(Dp[1][i][j][s^(1<<j)],val);
						if(Mp[i][j-1]) add(Dp[1][i][j][s^(1<<(j-1))],val);
					}
				}
				else if(!pl1&&pl2) add(Dp[op][i][j][s^(1<<j)],val);
				else if(pl1&&!pl2) add(Dp[op][i][j][s^(1<<(j-1))],val);
			}
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M);
	St[0]=1,Ed[0]=N+1,Nxt[0]=1,Bg[0]=1,Fl[0]=M+1;
	St[1]=N,Ed[1]=0,Nxt[1]=-1,Bg[1]=M,Fl[1]=0;
	for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) read(Mp[i][j]),Mp[i][j]^=1;
	S=(1<<(M+1))-1;
	Dp[0][0][M][0]=Dp[1][N+1][1][0]=1;
	solve(0),solve(1);
	for(int i=1;i<=N;++i)
		for(int j=1;j<=M;++j)
		{
			if(!Mp[i][j]) continue;
			int pos=S^(1<<(j-1))^(1<<j);
			for(int s=pos;s;s=(s-1)&pos) add(ans[i][j],(ll)Dp[0][i][j-1][s]*Dp[1][i][j+1][s]%Mod);
			add(ans[i][j],(ll)Dp[0][i][j-1][0]*Dp[1][i][j+1][0]%Mod);
		}
	for(int i=1;i<=N;++i,puts(""))
		for(int j=1;j<=M;++j) write(ans[i][j],' ');
	return 0;
}
/*

*/
相关文章