头插DP指北

UPD:排版已挂。先去洛谷看吧,这边待修。

洛谷ID:GNAQ

 

UPD:我稍微改了一下封面图片,现在它成了真 · 插头DP了 😕

插头DP的概念(据我不可靠考证)最早出现在08年CDQ的论文中,而此类题目早在04年前后就已经存在。

(***下面假设聚聚们都会了状压DP……)


1.什么是插头DP

插头DP (PlugDP ,By yhzq),也就是一类基于连通性的状态压缩动态规划,是用状压DP处理联通问题的强劲武器。

常见的类型有棋盘插头DP和CDQ论文里的两个非棋盘上的模型。

常见的联通问题:多回路问题、路径问题、简单回路问题、广义路径问题、生成树问题


2.插头DP的大致思路


2.1 划分阶段

大家都知道了这是基于联通性的状压DP,所以本质上还是状压DP。

一般设dp[i][j][state](i,j)位置,状态为mathrm{state}的方案数(或者代价,等等让你求的东西……)

所以我们状压什么呢?轮廓线。

DP求解棋盘问题是逐格转移的。所以已经转移过的格子和没转移过的格子被一个折线分成了两半儿。这个折线就是轮廓线。

@远航之曲的简洁解释:已决策格子和未决策格子的分界线)

就这个蓝线(现在转移的格子是第3行第3个)。

插头又是什么呢?一个格子有四个插头,一个存在的插头表示在它代表的方向上能与相邻的格子连接(联通)。不存在就不能。

为什么要引入插头?要求一个回路,也就意味着最后所有的非障碍格子通过插头连接成了一个连通块,因此转移时需要记录格子的连通情况。

我们递推的时候就是依据轮廓线上的插头存在性,求出所有能转移到的合法状态

显然回路问题中一个格子恰好有两个插头,一个是“进来”的一个是“出去”的。


2.2 记录状态

最小表示法

所有的障碍格子标记为 0 ,第一个非障碍格子以及与它连通的所有格子标记为 1 ,然后再找第一个未标记的非障碍格子以及与它连通的格子标记为 2 ……重复这个过程,直到所有的格子都标记完毕。比如连通信息((1,2,5),(3,6),(4)) 表示为{ 1,1,2,3,1,2 }

(还有一种最小表示法,即一个连通块内所有的格子都标记成该连通块最左边格子的列编号。)

括号表示法

【性质】轮廓线上从左到右 4 个插头 a, b, c, d,如果 a, c 连通,并且与 b 不连通,那么 b, d 一定不连通。这个性质对所有的棋盘模型的问题都适用。证明详见CDQ论文。

“两两匹配”,“不会交叉”这样的性质,我们很容易联想到括号匹配。

将轮廓线上每一个连通分量中左边那个插头标记为左括号,右边那个插头标记为右括号,由于插头之间不会交叉,那么左括号一定可以与右括号一一对应,这样我们就可以使用 3 进制, 0 表示无插头, 1 表示左括号插头, 2 表示右括号插头,记录下所有的轮廓线信息。不妨用#表示无插头,那么上面的三幅图分别对应的是 (())#(),(()#)(),(()###) ,即 (1122012),(1120212),(1120002) ,这种表示方法称为括号表示法。

状态的编码

对于最小表示法,编码最简单的方法就是表示成一个 n+1 位的 p 进制数, p 可以取能够达到的最大的连通块标号加 1 。在不会超过数据类型的范围的前提下,建议将 p 改成 2 的幂,因为位运算比普通的运算要快很多。

如需大范围修改连通块标号,最好将状态 O(n) 解码到一个数组中,修改后再 O(n) 计算出新的 p 进制数,而对于只需要局部修改几个标号的情况下,可以直接用 (x ;mathrm{div}; p^{i-1} ) ;mathrm{mod}; p 来获取第 i 位的状态,然后 +k times p^{i-1} 直接对第 i 位进行修改。


2.3 转移状态

首先,因为逐行递推要讨论的情况还是比较难处理的,除非要求解的问题特别适合这样做,要不然我们一般使用逐格递推,这样可以方便讨论情况。

一般来说轮廓线上有不少状态都是无用的,而且一般来说插头DP的状态数很多,所以我们使用一个技巧来加速,那就是,我们用一个线性数据结构(我愿意开一个/模拟一个vector)来存储状态,每次读取上一格的所有合法状态扩展,而不是xjb枚举状态来扩展。

然后,我们来研究一下怎么转移。我们看一种题型吧。

给你一个 m times n 的棋盘,有的格子是障碍,问共有多少条回路使得经过每个非障碍格子恰好一次。

m, n \leqslant 12

1.新建一个连通分量

这个情况只出现在转移位置的轮廓线上没有下插头和右插头。

如图。然后我们只有一种转移方式就是当前格做右插头和下插头。

括号表示法就是新建一对紧挨着的左右括号。最小表示法就直接解码重编一下。

2.合并两个连通分量

如果当前轮廓线上既有右插又有下插,那你只能当前格做左插和上插,要不然就不是回路了。

然后如果右插和下插联通,那这种情况只能是在最后一个非障碍格是合法的。

不连通的话,当然这样做会把他们变联通,看图:

括号表示法里就直接删一对括号,最小表示法还是解码重编。

3.保持原来的连通分量

当轮廓线上只有下插或者右插,就只能当前格做一个左插/上插来满足回路性质,剩下一个插头是随便安排的。

图:

括号表示法的话就把下插/右插对应的括号移到你加的插头上就行了。

最小表示法也类似,把下插/右插位置的记号移到你加的插头对应位置就行(因为是延续了一个连通分量)。

注意当从一行的最后一个格子转移到下一行的第一个格子的时候,轮廓线需要特殊处理。这个看代码最好解释了。

(还要多啰嗦一句,一般状态编码的左右和轮廓线的左右是反着对应的……也就是编码最右面一位是对应轮廓线最左面格子)

一个小优化

有时候你转移的时候有可能从两个不同状态转移出同一个状态,这个时候我们用hash优化它就好了。hash表的实现用挂表法就行。

还有提取每个插头状态的时候我们可以预处理一个对应bit的数组,然后用上文提到的解码方式去解码。

这儿还是曲神@远航之曲的trick,他讲的很明白。


然后我们就讨论完了插头DP的第一道入门题该怎么做,题目提交在这儿:1519. Formula 1

我真的是抄的曲神的代码,曲神码风和实现都太棒了!


··
·····


state是表示状态,dp表示方案数。这里用了滚动数组来优化空间(pre,cnt来滚动)


bits是一个方便提取插头的数组。比如bits[3]=6,那提取第三个格子上面和左面的插头(分别叫做is_d和is_r)就是state>>bits[3-1]和state>>bits[3]


我们存储状态是四进制,括号表示法。1表示(,2表示) 。


hash表的内部实现你可以看到就是一个链表。(struct hash_table)


·····


因为可能最后一格也有障碍,所以要记录一下最后一个无障碍格子(endx,endy)


··


添加状态压进hah()函数里了。


·

·

·····


一开始要初始化dp(0,0)=1


·


77行,这是为了转移到下一行的时候处理第一个格子的is_r插头(建议在纸上模拟一下)


····


case 0:有障碍。

case 1:

case 2:

case 3:

case 4:(要改插头)

case 5:(要改插头)

case 6:(要改插头)

case 7:形成一个回路。只有最后一个格子才能形成一个回路。

P.S.为了做上面那个效果我拿Elementary Editor搞了半小时……

To be continued……

再来一道毒题 P3886 [JLOI2009]神秘的生物

唉。这题我写了差不多四天……还是真的菜。

首先说明的是这份代码来自vawait大佬 (肽聚了,写了无数插头DP……)

这道题还有一个很有意思的背景:

仔细想想你会发现SRM312好像是06年的比赛……

JLOI居然抄原题,差评

还有就是其实经过我的深刻反思,我意识到……

原题卡好几天!……

唉 我应该把论文和课件都看一遍的TAT

有一种策略就是我们可以只转移有左插和上插的格子。可惜其实这是很不对的一个策略,你没法应付像这样:

真令人头秃。那怎么办呢? 🙄

一些注意事项

首先你会发现,因为四个插头都是本质相同的,所以我们大可以用一个插头去概括它,也就是说,本题所谓的轮廓线是这样的:

也就是我们只需要保存 n 个格子的最小表示就可以转移了。稍加分析可以得到我们需要八进制来表示这么多格子的最小表示。


转移状态

按照一贯的套路我们又要讨论如何转移状态。基于对联通信息的维护,我们会有:

1.当前格无插头

2.当前格有插头

2.1 当前格属于“新建一个联通分量”

2.2 当前格加入之前的联通分量

所以一共有三种转移。

1非常好做。去掉即可。

2.1 非常好做,我们可以用 7 来表示新建的联通分量

2.2 从vawait大佬那里看到了一个实现上的技巧就是让当前的最小表示等于 mathrm{max(Dplug,Rplug)} 。然后让所有最小表示为 mathrm{min(Dplug,Rplug)} 的也等于它。


判定状态合法性

这个题和之前的不一样,因为答案并不是最后更新,转移完之后状态也都不一定是合法的。

所以hash之前应该先判一下状态的合法性

1如果没有下插,或者下插(也就是当前格的上面一格)与轮廓线上其他格联通,那这样转移是合法的,反之一定不合法。

2.1和2.2是一定合法的。


更新答案

hash之前要重新编码,编码完之后如果当前轮廓线上有一个或零个联通分量都是满足题目要求的状态,可以更新答案。


hash

还是和之前一样。不过我从vawait的代码里get到一个卡空间的技巧,就是把dp状态也压进hash表里。感觉也不难写。


重新编码

思路还是挺简单的。唯一需要合并联通分量的地方2.2也已经提前处理好了。

GNAQ的文化课颓废[指南]

1.

前一阵子当然挺颓的,不是熬夜打Cf就是出毒题,感觉成绩完全完蛋。

好像该背的语文历史政治都没背。。。

还作了个大死,月考前一天颓Div3……

想什么呢,当然没考好啊……英语AK失败,被同学虐了。

然后当然是班主任提了一句……我说要来济南跟着省队集训班主任也不太高兴……

但是其实省队集训这事我也没料到……只好搬出Yansir……

……不管了,反正最近上课各种没效率。。

 

2.

然后走的某一天在某乎被关注了……就看了看……好像是本校的学生……

唉不对啊……本校的哪有知道我id的……肯定又是某W姓选手干的。

唉……烦……私信问问她是谁吧。。

结果倒是反问我了。我答了一句,她就不说了。

然后好像是集训前一天中午,翻了翻这人主页。

班里第一 男同学 数理化成绩加起来赶超重点班的emmm(数学课经常是我们听老师讲课他自己自学选修的一些东西…)

先说语文 期中考试刚过 语文124(普通班最高的成绩啦23333) 一雪第一次月考语文89不及格的前耻…现在做的是全国卷小说这方面的题不是很多 ……

哎呀?!……

然后GNAQ就突然感觉鼻子一酸,什么话也说不出来了。

GNAQ在的重点班,学习氛围并不是很好,大家都很盼望能放假玩一会儿。

好像是学校要求多上课,剥夺了一部分假期,就可以理所应当的整天无心学习,盼望放假一样。

当然GNAQ也不是抱怨成绩不好是因为这个原因,但是总归学习氛围好一些的话,大家都会再试着努力,多努力一些,不是么?

 

3.

GNAQ思考了很长时间。GNAQ觉得自己不服气,觉得自己不能做到这么好说明自己没有用心。

GNAQ觉得自己也有些懈怠了。GNAQ以为普通班不会”威胁”到重点班,或者可以说以为普通班的第一名也不如重点班中游的同学们。

GNAQ觉得自己反正考了一次第11名,就有了这样的实力。GNAQ最近好像怎么也找不到状态,能像冬天那样拼命的学文化课了。

好像也不是因为OI的原因。寒假之前也会晚上抽时间去写题,但是现在效率慢慢就低了。

GNAQ真的没有意识到,自己的水平已经下滑到了什么程度。GNAQ知道明明自己搞OI的时候稍微努力一下,文化课也可以考的很好,也不会被老师们找来找去。

但是GNAQ真的不知道该怎么做了。GNAQ知道自己哪些学科弱,但是在刷题和听课之后并不能主动让分数变高,只知道下一次考试的分数一定又是rand()。

还有,GNAQ化学跟不上了啊,GNAQ英语再也没有全市第一的水平了。

 

4.

马上期末学业考试了,GNAQ要更加努力才对。

GNAQ决定要更加有效率一些。GNAQ甚至可以允许自己上课的时候先自己补一下基础。

当然,GNAQ也意识到了分数下滑主要是因为基础理解的太浅了。

GNAQ决定期末考一定要让自己满意。GNAQ想刷榜,想和大家一起开心。

 

最后的最后,GNAQ最近在某乎看到一个回答,挺感动的,放在这里吧。https://www.zhihu.com/question/51343040/answer/215199069

 

通过移位形成的置换群的轮换数

有这样一个结论,n个元素的置换群通过移k位形成的置换数是 \gcd(n, k)
例如 n = 6, k = 2 的置换群的置换数是 \gcd(6, 2) = 2

0 1 2 3 4 5
2 3 4 5 0 1

形成的置换是 [2, 4, 0][3, 5, 1]

考虑一下为什么是这样的,一个直观的入手点就是尝试几个例子,然后分析一下置换是怎样形成的,清楚了这个自然也就明白了置换数会是多少。

  • 假设我们移位 k,并且从 \rm base 位置开始寻找置换,那么置换将会是 (kx + \mathrm{base} )\mod n \; (x \in \mathbb{N} ) 得到的数字。

例如 n = 9, k = 6

0 1 2 3 4 5 6 7 8
6 7 8 0 1 2 3 4 5

\rm{base} = 0 位置对应开始

\begin{array}{c} 6 \times 1 \mod 9 = 6 \\ 6 \times 2 \mod 9 = 3 \\ 6 \times 3 \mod 9 = 0 \\ \end{array}

\rm{base} = 1 位置对应开始


\begin{array}{c} (6 \times 1 + 1) \mod 9 = 7 \\ (6 \times 2 + 1) \mod 9 = 4 \\ (6 \times 3 + 1) \mod 9 = 1 \\ \end{array}

\rm{base} = 2 位置对应开始

\begin{array}{c} (6 \times 1 + 2) \mod 9 = 8 \\ (6 \times 2 + 2) \mod 9 = 5 \\ (6 \times 3 + 2) \mod 9 = 2 \\ \end{array}

对于这个例子观察发现,形成的置换貌似就是\mathrm{mod}\; \gcd(n,k) 的同余类。

看看这是不是正确的,前面的分析过程使我们将置换转换为 (kx + \mathrm{base} ) \mod n 这样的一个式子, 也就是说这个式子的结果根据 \rm base 的不同为什么会形成\mathrm{mod}\; \gcd(n,k) 的同余类。

我们在这里让 \mathrm{base} < n ,于是我们有:

(kx + \mathrm{base}) \;\mathrm{mod}\; n = kx \;\mathrm{mod}\; n + \mathrm{base}

这样我们可以只分析 kx \mod n 这一部分。

我们让 kx \;\mathrm{mod}\; n \equiv ky \;\mathrm{mod}\; n

所以 k \cdot (y-x) \;\mathrm{mod}\; n = 0

x = 0 时,ky \;\mathrm{mod}\; n = 0 ,这就意味着我们要证明满足此式子的 y > 0\min x\frac{n}{gcd(n,k)}

我们假设 x < \frac{n}{gcd(n, k)} 且满足上式时,kx | n,而且显然 kx | m ,那么 kx 就是 nk 的最小公倍数 。

但是 kx < k \cdot \frac{n}{gcd(n,k)} ,右边才是最小公倍数,所以当 x < \frac{n}{gcd(n, k)} 时,不满足 k \cdot (y-x) \;\mathrm{mod}\; n = 0

所以满足上式的 \min x=\frac{n}{gcd(n,k)}。这也就是轮换的个数是 \frac{n}{gcd(n,k)}