P7418 [USACO21FEB] Counting Graphs P

· · 题解

部分借鉴了自己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}

解释：

接下来考虑转移 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}

解释：

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

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

解释：

至此 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}}

解释：

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

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

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

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

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

Upd：补充解释。

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