ABC 386 G — Many MST

考察

M通りの各辺重みについてM^{N choose 2} graphを直接列挙できない。MST重みはthreshold k未満の辺からなるgraph G_kの連結成分数の和として表せ、重み付き問題を各kの無向graph数え上げへ分解できる。

Σ_G c(G_k)はgraphを先に数えるのでなく、その連結成分として選ばれる連結部分graph Hを先に固定する主客転倒で扱える。

採用する候補: MST重みをthreshold成分数へ変換し、連結graphの重み付き数え上げDPを各kで行う

頂点数sの指定連結成分の寄与を、頂点1を含む成分を引く標準DPでO(N^2)計算でき、全kでもO(N^2M)がN,M≤500に適合する。

棄却する候補: 各edge重み付けを列挙してKruskal法を実行する

候補はM^{N(N-1)/2}個で指数的であり、個々のMSTを構成できない。

0..M-1重みへshiftすると、MST重みはΣ_{k=1}^M c(G_k)-Mとなり、最後に元の重みshift分を補正する。

kを固定し、f_sを「指定したs頂点への全辺重み割当のうち、k未満の辺だけで連結になる割当数」と定める。f_1=1であり、非連結な割当を頂点1の属する成分サイズiで一意に分類すると、

f_s = M^{s(s−1)/2}
      − Σ_{i=1}^{s−1} C(s−1,i−1) f_i
        (M−k)^{i(s−i)} M^{(s−i)(s−i−1)/2}

となる。C(s−1,i−1)は頂点1と同じ成分の頂点選択。残る三因子は、成分内部の割当f_i、成分を切り離す境界辺のM−k通り、外側の自由な辺のM通りである。

全割当にわたる成分数の和T_kは、各成分の頂点集合を一つずつ選んで

T_k = Σ_{s=1}^N C(N,s) f_s
      (M−k)^{s(N−s)} M^{(N−s)(N−s−1)/2}
answer = Σ_{k=1}^M T_k + (N−1−M) M^{N(N−1)/2}

と得る。定数補正は各graphのthreshold和からMを引き、重みを元に戻すN−1を足す分。N=2ならT_k=2(M−k)+k=2M−kとなり、答えはM(M+1)/2、一本の辺の重み1..Mの総和と一致する。

二項係数とMの冪を用意し、各kでf_sをsの昇順に埋めてT_kへ足す。各指数は辺本数であり、外部頂点が0個でも0^0=1とする。最後に定数補正を含めてmod 998244353で出力する。

典型の発動条件

MST重みのthreshold積分

発動条件: 全edge重みの分布上でMST総和・期待値を数えたいとき。

各thresholdでの連結成分数を足す式へ変換する。

連結graph数え上げDP

発動条件: labelled graphの全体からconnectedなものだけを取り出すとき。

頂点1を含むcomponentを固定し、非連結caseをsize別に引く。

主客転倒

発動条件: graphごとのcomponent数総和を直接数えにくいとき。

component候補Hを固定して、それを成分に持つgraph数を数える。

問題固有の要素

MSTそのものの組合せを追わず、Kruskalで各重み層が答えへ寄与する量を連結成分数として線形化する。

別の問題へ持ち帰る視点: 全入力に対する最適構造の総和では、目的値をthreshold indicatorの和へ分解し、各層の構造数を数える。

正当性

Kruskalで重みk未満のgraphの成分数は、MSTでk以上の辺を何本必要とするかに1を加えた値。threshold和と定数補正が各graphのMST重みに一致する。成分数総和は成分subsetを先に固定し、内部connected重み数・境界高重み・外側自由辺数を掛けて数える。anchor再帰が内部connected数を一度抽出するので全graphのMST総和が得られる。

実装上の注意

  • 重みを0..M-1へshiftした補正符号、k未満/以上の選択肢数kとM-k、edge本数の指数を混同しない。0^0は1として扱う。

復習の核

  • N≤4,M≤3で全edge重みを列挙してKruskal結果を足し、各kの成分数総和と最終shift補正を独立に照合する。

計算量と制約

時間

O(MN²)。二項係数とMの冪をO(N²)で用意し、各thresholdでM−kの冪と連結成分DPをO(N²)で計算する。

空間

O(N²)。二項係数表、Mの冪表、現在のthresholdのM−kの冪表、f_s。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 2 \le N \le 500; 1 \le M \le 500; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Many MST の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: label付き連結成分分解・exponential formula

主題
追加で学ぶ技能
既習技能

主タグ: 寄与の数え上げと順序交換 label付き連結成分分解・exponential formula

補助タグ: 組合せ係数・数え上げ

執筆: abc-explanation-author1.1.1 / revision 2

学習の位置

体系上の位置: label付き連結成分分解・exponential formula

  • 最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。
  • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

先に読む単元:

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題