ARC 044 B - 最短路問題

• 問題
• AC

とりあえずソートしてランレングス圧縮して、同じ距離の頂点グループ毎にグラフを作っていくことを考える。距離$0$は頂点$1$だけとか、距離が飛んでいる部分があってはいけないとか、そういうケースは最初に考慮しておく。

頂点$1$からの距離が$i$の頂点が$B_i$個あるとする。距離$i$の頂点同士はどうつないでもほかの頂点と$1$との距離に影響しない。したがって、$\binom{B_i}{2}$通りのペアすべてに自由に辺を張れるので、距離$i$に対して$2^{\binom{B_i}{2}}$通りの辺の張り方があることになる。

次に、距離$i-1$の頂点グループと距離$i$の頂点グループをつなぐ辺の張り方を考える。これもだいたい自由に辺を張れるのだが、距離$i$の頂点は、距離$i-1$の$B_{i-1}$個の頂点のうち少なくとも1つにはつながれていなければならないという制約がある。「少なくとも1つ」は包除原理で書ける:

$\begin{aligned} & 2^{B_{i-1}B_i} - \binom{B_i}{1}2^{B_{i-1}(B_i-1)} + \binom{B_i}{2}2^{B_{i-1}(B_i-2)} - ... + (-1)^{B_i}\binom{B_i}{B_i}2^{B_{i-1} \cdot 0} \\ = & \sum_{k=0}^{B_i} \binom{B_i}{k}(-1)^k(2^{B_{i-1}})^{B_i-k} \\ = & (2^{B_{i-1}}-1)^{B_i} \end{aligned}$

あっ……

---

包除で求めてから自明な数え方に気づくパターン、これで3回目くらい。