[ARC044B] 最短路問題

[ARC044B] 最短路問題

难度：\(1744\)
标签：最短路，记数
\(\mathtt{blog}\)

有一个 \(n\) 个点的无向图，\(1\) 点为起点，现在告诉你 \(1\sim n\) 点到 \(1\) 点的最短距离，每条边的长度为 \(1\)。

问有多少种连边方式满足条件。

设 \(a_i\) 为距离为 \(i\) 的点的个数。

可以发现，距离为 \(i(i>0)\) 的点的距离仅可能从距离为 \(i-1\) 的点距离 \(+1\) 推来。则距离为 \(i\) 的每个点都与距离为 \(i-1\) 的点至少有一条连边，则一个距离为 \(i\) 的点的贡献便是 \(2^{a_{i-1}}-1\)，因为要排除没有连边的情况需要 \(-1\)。因此可以推出所有距离为 \(i\) 的点的贡献是 \((2^{a_{i-1}}-1)^{a_i}\)。

同时除了“有影响”（即由此改变了距离，上文提到）的边，还有距离 \(i\) 内的互相连边，这些边是“无影响”的，每条边都可以选或者不选，贡献为 \(2^{\frac{a_i\times(a_i-1)}{2}}\)。

整理可得：\(ans=\prod_{i=1}^{mx}(2^{a_{i-1}}-1)^{a_i}\times2^{\frac{a_i\times(a_i-1)}{2}}\)，\(mx\) 为最大距离。

无解情况就很好推了：

1. \(1\) 点为起点距离 \(\not=0\)。
2. 除 \(1\) 点外都不为起点距离 \(=0\)。
3. 没有距离为 \(i-1(1\le i\le mx)\) 的点推向距离为 \(i\) 的点。

这道题需要在结尾输出换行。

\(\mathtt{Code}\)