[ARC044B] 最短路問題
Atcoder Luogu VJudge
难度：\(1744\)。
标签：最短路，记数。
有一个 \(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\) 点为起点距离 \(\not=0\)。
- 除 \(1\) 点外都不为起点距离 \(=0\)。
- 没有距离为 \(i-1(1\le i\le mx)\) 的点推向距离为 \(i\) 的点。
这道题需要在结尾输出换行。
标签：连边,记数,le,好题,距离,mx From： https://www.cnblogs.com/lhzQAQ/p/16992408.html