【模拟赛】沼泽地（插头DP）_小红闯沼泽地

背景

(创作声明：包含虚构创作)

自从阴暗潮湿的沼泽地里莫名其妙生长出红树的那一刻起，有一种传说中的红皮肤怪物诞生了。
它们在沼泽莲叶上发出诱人的声响，它们身形小巧，穿梭于水草和藤蔓之间。
第一天便有经过的傻子村民被它生吞。村民们找遍了沼泽外围，连尸体都没看见。和他一齐失踪的还有常年在附近山地生活，偶尔下沼泽地喝水的一只山羊。
第二天，村民们隔着老远听到女巫的惨叫。当提着剑和牛奶的村民们赶到附近时，只见到红皮肤魔头远遁的身影。
村民们一向惧怕的女巫，也未能幸免。
沼泽附近的村庄笼罩在恐惧的阴霾中。
……
几个月后，一位身着蓝色铠甲的勇者来到村庄，他有很多东西，与村民们进行了友好的交易，借住在村民的小木屋里。不大的村庄里充满了快活的空气。后一天村民们发现，一直以来守护村庄的强大铁人不见了。
那一天，村民们回想起了被红皮肤魔头支配的恐惧。
勇者决定亲自去沼泽地探查，我和另外几个胆大的村民跟了上去。
结果却极其惨烈……上帝啊！我们为勇者默哀！
当我们到达沼泽地外围时，就迎面遇上了魔头！勇者毫无戒备地走了过去，说：“这不就是个……”
话音未落，他就被魔头一口吞掉了！
我们逃得很慌，根本来不及回头看，只听见魔头近似嬉笑的响声渐渐远去……
  ~  
——沼泽村庄图书馆：《村民回忆录》

题面

当Mojump更新了1.19快照版本时，std通过摸鱼了解了所有更新的内容，包括沼泽红树林，红色的青蛙，泥土等等……

他当然也知道了青蛙刚出来时有个特性，那就是吞噬一切，包括玩家。所以他打算到沼泽地去探险。

他开启了一个新地图，并出生在了一块 $n\times m$ 的沼泽地。该地有些位置的草地刚触及海平面，另一些位置则低了一格，被水填充。

std 现在有一个有意思的问题，由于种子特性，地图生成时该区域 $n\times m$ 个位置各有一个独立的概率 $a_{i,j}$ 会低一格，被水填充。他想知道最大的单个水池面积的期望大小。单个水池可以理解为一个被水填充的格子的极大四联通块。

$a_{i,j}$ 和答案都对 $998244353$ 取模。（并不是用多项式的暗示）

$1\le n,m\le 40,n\times m\le 40.$

题解

（由于题解极其简略，我多花了点时间在题面背景上摸鱼）

由于 $n\times m$ 不超过 40，所以 $n,m$ 的最小值不超过 6，我们不妨设 $n\le m$ ，那么我们可以维护当前列的连通性、每个连通块的大小、扫过的连通块的最大大小——作为状态（!）设计DP。

当你用精心打磨出的大模拟爆搜对总合法状态数进行计算后，会发现它最大在 $1.6e5$ 左右。

实现上，把连通性用最小表示法后，大可直接用 map 存 DP 状态（pair<int,string>，最大大小和连通块大小都不超过 40，可以用 char）然后带一个 $\log$ 的全局复杂度加成进行计算。不然，可能有亿点麻烦。

最终用插头DP的方式转移，总时间复杂度 $O(可过)$ （两个$\log$？）。

CODE

pair 的第一位存的是最小表示法，第二位的 string 第一个位置存最大连通块大小，后面的位置存当前列每个连通块的大小。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 500005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
//#define getchar() xchar()
LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 998244353;
int n,m,s,o,k;
int a[45][45],pr[45][45];
int id[5000005],to[5000005],tp[5000005],cnt;
int findd(int S) {
	int ty[10] = {},xx = S,a[10],cn = 0,c2 = 0,rs = 0;
	while(xx) a[++ cn] = xx%10,xx /= 10;
	for(int i = cn;i > 0;i --) {
		if(a[i] && !ty[a[i]]) ty[a[i]] = ++ c2;
		rs = rs*10+ty[a[i]];
	}return id[rs];
}
string ep = "0";
pair<int,string> dw(int S,string b) {
	int ty[10] = {},xx = S,a[10],cn = 0,c2 = 0,rs = 0,mx = b[0];
	int bu[10] = {};string re = ep; re[0] = (char)mx;
	for(int i = 1;i < (int)b.size();i ++) bu[i] = b[i];
	while(xx) a[++ cn] = xx%10,xx /= 10;
	for(int i = cn;i > 0;i --) {
		if(a[i] && !ty[a[i]]) ty[a[i]] = ++ c2,re += (char)bu[a[i]];
		rs = rs*10+ty[a[i]];
	}return {rs,re};
}
void dfs(int x,int mx,int S) {
	if(x > n) {
		id[S] = ++ cnt;
		to[cnt] = S; tp[cnt] = mx;
		return ;
	}
	for(int i = 0;i <= mx+1;i ++) {
		dfs(x+1,max(mx,i),S*10+i);
	}return ;
}
map<pair<int,string>,int> dp,pd;
int pw[10];
int main() {
	freopen("memory.in","r",stdin);
	freopen("memory.out","w",stdout);
	n = read(); m = read();
	int mx = 0;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			pr[i][j] = read();
			mx = max(mx,pr[i][j]);
		}
	}
	if(n > m) {
		swap(n,m);
		for(int i = 1;i <= n;i ++) {
			for(int j = 1;j <= m;j ++) {
				a[i][j] = pr[j][i];
			}
		}
	}
	else {
		for(int i = 1;i <= n;i ++) {
			for(int j = 1;j <= m;j ++) {
				a[i][j] = pr[i][j];
			}
		}
	}
	dfs(0,0,0);
	pw[0] = 1;
	for(int i = 1;i <= n;i ++) pw[i] = pw[i-1]*10;
	for(int i = 1;i < pw[n];i ++) {
		id[i] = findd(i);
	}
	ep[0] = (char)0;
	dp[{0,ep}] = 1;
	for(int c = 1;c <= m;c ++) {
		for(int r = 1;r <= n;r ++) {
			pd.clear(); swap(pd,dp);
			for(auto i = pd.begin();i != pd.end();i ++) {
				int mx = i->FI.SE[0],s = i->FI.FI;
				string bu = (i->FI).SE;
				int l = (s/pw[r-1])%10,u = (r==1 ? 0:(s/pw[r-2])%10);
				pair<int,string> nx = dw(s-l*pw[r-1],bu);
				(dp[nx] += i->SE*1ll*(MOD+1-a[r][c])%MOD) %= MOD;
				if(a[r][c]) {
					if(!l && !u) {
						int ma = tp[id[s]]; bu[0] = (char)max(mx,1);
						bu += (char)1;
						nx = dw(s+(ma+1)*pw[r-1],bu);
						(dp[nx] += i->SE*1ll*a[r][c]%MOD) %= MOD;
					}
					else if(!l || !u || l == u) {
						int ii = max(l,u);
						bu[ii] = bu[ii]+1; bu[0] = (char)max(mx,(int)bu[ii]);
						nx = dw(s-l*pw[r-1]+ii*pw[r-1],bu);
						(dp[nx] += i->SE*1ll*a[r][c]%MOD) %= MOD;
					}
					else {
						for(int j = 0;j < n;j ++) {
							if((s/pw[j])%10 == u) {
								s += (l-u)*pw[j];
							}
						}
						bu[l] += bu[u]+1; bu[0] = (char)max(mx,(int)bu[l]);
						nx = dw(s,bu);
						(dp[nx] += i->SE*1ll*a[r][c]%MOD) %= MOD;
					}
				}
			}
		}
	}
	int ans = 0;
	for(auto i = dp.begin();i != dp.end();i ++) {
		(ans += ((int)i->FI.SE[0])*1ll*i->SE%MOD) %= MOD;
	}
	AIput(ans,'\n');
	return 0;
}
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

后记

该特性的首次发现，便是一只青蛙吞了一只山羊。

“剑和牛奶”：众所周知，牛奶可以针对性地对女巫造成极大伤害（

勇者：“这不就是个癞蛤蟆？”

铁傀儡为什么消失了？这个不清楚，我只知道勇者的背包里多了四块铁锭。