ARC 093 E - Bichrome Spanning Tree

• 問題

問題概要

N頂点M辺の重み付き無向グラフと整数Xが与えられる. この辺を2色に塗っていく.
次の条件を満たす辺の塗り方の数をmod 1e9+7で求めよ.
- 2色どちらの色も含む全域木が存在して,そのような全域木の最小コストがXである.
1 <= N <= 10³, 1 <= M <= 2*10³, 1 <= X <= 10¹²

解法

全域木の集合を考えながら問題文を噛み砕いていくと条件は以下のようになる.
(1) 単色でない(2色どちらも含む)コストXの全域木が存在し,
(2) 単色でないコストX-1以下の全域木は存在してはいけない
(2)はつまり,コストX-1以下の任意の全域木に含まれる任意の辺は同じ色であるということになる.

ここである辺を含む最小全域木のコストはその辺を最初に使って,それから他の辺を小さいものから繋げていけば良いから,
a[i] := (全域木のうちで辺iを含むものの最小コスト) は O(M² * logM)で求められる.
f(x) := (aがx以下の辺が全て同色であるような塗り方) とすると,
num = aがx以下の辺の数として,
num = 0 => f(x) = 2^M
num!= 0 => f(x) = 2 * 2^M-num = 2^M-num+1

(2)を満たす塗り方の数はfを用いて表せ, f(X-1) となる.
そのような塗り方の中で,(1)を満たさない塗り方を考える.
これは a[i] = X であるような辺も X-1以下の色と同じに塗っている場合となる.
そのような塗り方の数は f(X) となるから,答えは f(X-1) - f(X) となる.

メモ

解けなかったので解説放送を見た. 日本語が難しい.

コード