【AGC035E】Develop（图论，DP）

news/2024/4/28 23:51:25/文章来源:https://blog.csdn.net/ez_lcw/article/details/127429609

对于某个集合 $S⊆{1,⋯,n}S\subseteq\{1,\cdots,n\}$ ，考虑能不能删去 $S$ 。

对于任意 $x∈Sx\in S$ ，连边 $x→x−2x\to x-2$ （如果 $x−2∈Sx-2\in S$ ）及 $x→x+kx\to x+k$ （如果 $x+k∈Sx+k\in S$ ），那么能把 $S$ 删去当且仅当这张图是一个 DAG。

于是我们先对所有点都这么连边形成图 $G$ ，那么 $S$ 合法当且仅当 $S$ 在 $G$ 中的导出子图是个 DAG，即无环。

对于所有 $x→x−2x\to x-2$ 的边，它们形成了两条链，分别称为奇链和偶链。然后我们对 $k$ 的奇偶性分类讨论：若 $k$ 是偶数，那么这两条链是不连通的（独立的），而无环相当于要求每条链中不连续选 $k /2 + 1$ 个点，这个方案数很好统计（注意数据范围不大，暴力 DP 即可）。

若 $k$ 是奇数，情况就复杂些。首先，若出现了环，那么一定经过了正偶数条 $x→x+kx\to x+k$ 的边（经过一次会改变一次当前点的奇偶性）。接下来我们证明，一个简单环必定只经过了恰好 $2$ 条 $x→x+kx\to x+k$ 的边。

对于任意一个简单环 $C$ ，取其编号最小的点 $a$ ，那么环中 $a$ 的上一个点一定是 $a + 2$ ，下一个点一定是 $a + k$ （记为 $b$ ）。而且我们发现，对于 $a,a+2,⋯,b−1a,a+2,\cdots,b-1$ 中的任意一个点 $x$ ， $x$ 在环中都不可能是 $+ k$ 得到的（否则 $a$ 不是最小点），于是我们已经可以确定 $C$ 的一部分形态，如上图左上。

接着， $b$ 在环中接下来肯定是先走若干步 $- 2$ （可以是 $0$ 步，但不能超过 $a$ ）走到 $c$ ，然后再走一步 $+ k$ 走到 $d$ ，如上图左下。

接着，如上图右，我们又继续考虑 $e = b + 1$ 这个点是从哪来的，若它是 $+ k$ 得到的，那么就必然要经历从 $b - 1, b$ 右侧到 $b - 1, b$ 左侧的过程（从 $d$ 经过若干步到达 $a + 1$ ），这个过程中一定会再次经过 $b - 1, b$ 中的某一个点，这就与该环是简单环矛盾了。从而， $e$ 是从 $e + 2$ 来的。类似地，可以推出 $b+1,b+3,⋯,d−2b+1,b+3,\cdots,d-2$ 中的每一个点 $x$ 都是从 $x + 2$ 来的，这就和 $d$ 接起来了。

于是 $C$ 只有可能是 $a→一步+kb→若干步−2c→一步+kd→若干步−2aa\xrightarrow{\text{一步}+k}b\xrightarrow{\text{若干步}-2}c\xrightarrow{\text{一步}+k}d\xrightarrow{\text{若干步}-2}a$ 的形态。

那么，现在限制改为了， $S$ 在 $G$ 中的导出子图不能出现环，且该环恰经过两次 $+ k$ ，如下图左上。

在这里插入图片描述

假设 $S$ 已经选好了，怎么快速判断是否存在这样的环：可以从每个 $S$ 中的奇数编号的点 $x$ 开始，按如下方式找一条路径（称为 $x$ 的找环路）并检查：

找到最小的 $y$ 使得 ${y,y+2,⋯,x−2,x}⊆S\{y,y+2,\cdots,x-2,x\}\subseteq S$ 。
找到最小的 $z$ 使得 $z∈{y,y+2,⋯,x−2,x}z\in\{y,y+2,\cdots,x-2,x\}$ 且 $z+k∈Sz+k\in S$ 。若找不到这样的 $z$ 那么跳过从 $x$ 开始的检查。
找到最小的 $w$ 使得 ${w,w+2,⋯,z+k−2,z+k}⊆S\{w,w+2,\cdots,z+k-2,z+k\}\subseteq S$ 。
考虑路径 $P=x→x−2→⋯→z→z+k→z+k−2→⋯→wP=x\to x-2\to \cdots\to z\to z+k\to z+k-2\to \cdots\to w$ ，若 $P$ 长度大于等于 $k + 2$ ，那么我们就找到了一个环。

如上图左下，图中的红蓝两条路径就是从两个不同的 $x$ 开始的找环路。

容易证明，按照上述方式，若找不到任何一个环，那么图中就确实不存在环（因为从我们所述的 $z$ 跳到 $z + k$ ，是能使得 $P$ 的长度尽量大的）。

那么考虑 DP。如上图右，设 $fi,ℓ1,ℓ2f_{i,\ell_1,\ell_2}$ 表示考虑完 $[1, i]$ 中的奇数点和 $[1, i + k]$ 中的偶数点，其中从 $i$ 开始的找环路经过的点数为 $ℓ1\ell_1$ ，而从 $i + k$ 开始不断 $- 2$ 所能经过的点的个数为 $ℓ2\ell_2$ 的方案数。