自动搬运

查看原文

来自洛谷，原作者为

	约瑟夫用脑玩 AFO

搬运于2025-08-24 22:29:41，当前版本为作者最后更新于2021-08-11 10:21:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

部分借鉴了自己P7417的题解，相较于_Enthalpy的题解补充了每个转移每一步的解释。

首先特判二分图，不多赘述。

沿用P7417的定义，设一个点的奇最短路和偶最短路二元组为 $(x,y)$，且保证 $x<y$。

导致 $(x,y)$ 的方式仍然是：

1. 有另一个点奇偶最短路分别为 $(x-1,y-1)$，并连了一条边。
2. 有两个点分别为①$(x-1,y+1)$ 和②$(x+1,y-1)$，都连了一条边。注意当 $x+1=y$ 时，有 $(x+1,y-1)=(y-1,x+1)=(x,y)$。

解释：方式二中①的第一维保证较小最短路为 $x$，②第二维保证了较大最短路为 $y$，而他们的其他维由于与 $(x,y)$ 的点有直接连边故最大都只能 +1。

---

先按照 $x+y$ 为第一层阶段进行 DP，那么按方式一满足点的最短路是容易的，只用从上一阶段连边即可。

又因为方式二需要同阶段前后连边，于是再按 $x$ 为第二层阶段依次考虑。

而每个点要么按方式一满足，要么按方式二，要么两种都有，显然我们需要考虑只按方式二满足最短路的点对状态的影响，因为涉及到前后都必须连边。

设 $f_{x,y,p}$ 表示当前 DP 到 $(x,y)$ 的二元组，并且有 $p$ 个点还需要下一个状态连边，仅按方式二来满足最短路的方案。

那么我们通过枚举只按方式一满足最短路的点的个数来转移，设有 $q$ 个这种点，二元组 $(x,y)$ 的点总共有 $s1$ 个，二元组 $(x-1,y-1)$ 有 $s2$ 个，那么转移为：

$f_{x,y,p}=\sum_{q=0}^{s1-p}\binom{s1-q}{p}(2^{s2}-1)^{s1-p}g_{x,y,q}$

解释：

• $\binom{s1-q}{p}$：选点的方案系数，这里表示从 $s1-q$ 个不是 只按方式一满足 的点中选出 $p$ 个点只按方式二转移。
• $(2^{s2}-1)^{s1-p}$：连边的方案系数，不是 只按方式二满足 的点都需要方式一满足，每个点与 $(x-1,y-1)$ 的点至少连一条边。
• $g_{x,y,q}$：辅助转移数组，表示有 $s1-q$ 个点都有 $(x-1,y+1)$ 连边而来的方案。

---

接下来考虑转移 $g_{x,y,p}$，枚举上一次状态有多少个点需要当前状态回连边，设有 $q$ 个这种点，二元组 $(x,y)$ 的点总共有 $s1$ 个，二元组 $(x-1,y+1)$ 有 $s2$ 个，那么转移为：

$g_{x,y,p}=\binom{s1}{p}\sum_{q=0}^{s2}h_{s2,q,s1-p}f_{x-1,y+1,q}$

解释：

• $\binom{s1}{p}$：选点的方案系数，从 $s1$ 个点中钦定 $p$ 个。
• $h_{s2,q,s1-p}$：转移系数，表示在大小为 $s2$ 的集合和大小为 $s1-p$ 的集合之间连边，保证 $s2$ 中的 $q$ 个点和大小为 $s1-p$ 的集合度数至少为 $1$ 的方案。

---

考虑处理出 $h_{i,j,k}$，可以使用容斥，钦定有 $p$ 个 $j$ 中的点没有出度：

$h_{i,j,k}=\sum_{p=0}^j(-1)^p\binom{j}{p}(2^{i-p}-1)^k$

解释：

• $\binom{j}{p}$：选点的方案系数，从 $j$ 个点中钦定 $p$ 个。
• $(2^{i-p}-1)^k$：连边的方案系数，$k$ 个点中的每个与 $i-p$ 个未被钦定的点至少连一条边。

---

至此 DP 转移完毕，考虑统计答案，如果二元组恰为 $(x,y=x+1)$，则可以有点需要下一个状态连边，仅按方式二来满足最短路，这样的点可以以同类连边的方式消化掉，设二元组 $(x,x+1)$ 的点总共有 $s$ 个，贡献为：

$\sum_{i=0}^sT_{s,i}f_{x,x+1,i}$

解释：$T_{s,i}$：大小为 $s$ 的二元组集合中 $i$ 个点会通过同类连边消化掉的方案。

---

预处理 $T_{i,j}$，可以使用容斥，钦定有 $k$ 个点度数为 $0$：

$T_{i,j}=\sum_{k=0}^j(-1)^k\binom{j}{k}2^{\frac{(i-k)(i-k+1)}{2}}$

解释：

• $(-1)^k\binom{j}{k}$：容斥系数和钦定选点的方案系数
• $2^{\frac{(i-k)(i-k+1)}{2}}$：除去钦定的 $k$ 个点随意连边的方案数。

---

如果二元组不为 $(x,x+1\neq y)$，则不能有点需要下一个状态连边，贡献为 $f_{x,y,0}$。

把上述的公式拼起来就是一份代码了。

注意由于奇偶最短路最长可能出现 $2n$，涉及到二元组的数组及清空要开两倍。

Upd：修了公式里的小问题和语言表述，并补充了代码。

Upd：修了一下代码，将公式中的表述和代码中的变量整理统一了一下。

Upd：补充解释。

Upd：修改了之前不规范的地方。