ABC 321 G — Electric Circuit

考察

連結成分数を直接追う代わりに、「どの頂点集合が一つの成分になるか」を数える。集合内で閉じる配線は簡単に数えられるので、そこから非連結な配線を引いて、連結な配線を求めよう。固定した一頂点を含む成分に注目すると、引く対象を重複なく分けられる。

端子の対応を、頂点集合ごとに数える

部品を頂点、ケーブルを無向辺とみなす。同じ部品の赤青端子をつなぐ自己ループや、同じ二部品を結ぶ複数の辺も許される。端子は一つずつ区別するが、ケーブル同士は区別しない。赤い端子を順に見て、接続先の青い端子を一つずつ割り当てると、全体の配線は M!M! 通りになる。同じグラフになっても、端子の対応が違えば別の配線である。

すべての配線を作って成分数を数える方法は、M≤105M\leq 10^5 では使えない。一方、頂点数は N≤17N\leq 17 と小さい。そこで、端子の対応そのものではなく、頂点の部分集合を状態にする。

全頂点集合を V={1,2,…,N}V=\{1,2,\ldots,N\} とする。頂点 vv の赤い端子数を rvr_v、青い端子数を bvb_v とし、部分集合 S⊆VS\subseteq V 内の端子数を

r(S)=∑v∈Srv,b(S)=∑v∈Sbvr(S)=\sum_{v\in S}r_v,\qquad b(S)=\sum_{v\in S}b_v

と定める。まず f(S)f(S) を、集合内の全端子を使い、外へ一本も出さずに閉じる配線の数とする。各ケーブルは赤青を一つずつ使うため、両色の端子数が違えば閉じられない。一致して mm 個ずつなら、青い端子の割り当て方を数えればよい。

f(S)={m!r(S)=b(S)=m,0r(S)≠b(S).f(S)= \begin{cases} m! & r(S)=b(S)=m,\\ 0 & r(S)\neq b(S). \end{cases}

次に、非空集合 SS に対して g(S)g(S) を、集合内で閉じ、かつ SS 全体が連結になる配線の数とする。f(S)f(S) は複数の成分に分かれる配線も含むが、g(S)g(S) は含まない。赤青の端子数が違う場合は g(S)=0g(S)=0 でもある。

違いを見る独自の小例として、頂点1、2のそれぞれに赤青の端子が一つずつある場合を考える。集合 {1,2}\{1,2\} 内の配線は次の2通りだ。

  • 各頂点で赤青をつなぐ。自己ループが一つずつでき、成分は {1}\{1\} と {2}\{2\} に分かれる。
  • 頂点1の赤と頂点2の青、頂点2の赤と頂点1の青をつなぐ。二頂点が連結になる。

従って f({1,2})=2!=2f(\{1,2\})=2!=2 だが、g({1,2})=1g(\{1,2\})=1 である。「外へ出ない」だけでは、一つの成分とは限らない。

固定頂点を含む成分で、非連結な配線を一度ずつ引く

連結性を満たす配線を直接作るより、数えやすい f(S)f(S) から非連結なものを引きたい。しかし「連結な部分を一つ選ぶ」だけでは、一つの配線から複数の成分を選べてしまう。そこで SS の頂点を一つ固定し、それを含む成分だけを選ぶ。

先ほどの例を3頂点へ広げ、各頂点に赤青の端子を一つずつ置く。S={1,2,3}S=\{1,2,3\} とし、頂点1を固定する。非連結な配線で、頂点1を含む成分の頂点集合を TT とすると、候補は次の三つになる。

TTTT 内の連結な配線残りの集合内で閉じる配線積
{1}\{1\}g({1})=1g(\{1\})=1f({2,3})=2f(\{2,3\})=22
{1,2}\{1,2\}g({1,2})=1g(\{1,2\})=1f({3})=1f(\{3\})=11
{1,3}\{1,3\}g({1,3})=1g(\{1,3\})=1f({2})=1f(\{2\})=11

一行目の残り二頂点は、互いにつながっても、自己ループだけで別々になってもよい。そのため残りには gg ではなく ff を使う。全頂点に自己ループがある配線も、頂点1の成分は {1}\{1\} に一意に決まるので、一行目で一度だけ引かれる。

全配線は f(S)=3!=6f(S)=3!=6 通りだから、連結な配線は g(S)=6−(2+1+1)=2g(S)=6-(2+1+1)=2 通りとなる。これは三頂点を一周する、赤から青への二つの対応に当たる。

一般にも、非空集合 SS の固定頂点を aa とする。非連結な配線を、aa を含む成分の頂点集合 TT で分類する。TT は aa を含む真部分集合であり、成分内は g(T)g(T) 通り、残りは f(S∖T)f(S\setminus T) 通りで独立に選べる。従って

g(S)=f(S)−∑T⊊Sa∈Tg(T)f(S∖T)g(S)=f(S)-\sum_{\substack{T\subsetneq S\\a\in T}} g(T)f(S\setminus T)

となる。どの配線でも aa の属する成分は一つだけなので、各非連結な配線はちょうど一度引かれる。小さい集合の gg が分かれば、より大きい集合の gg を求められる。

一つの成分になる確率から、期待値へ戻す

ここまでの g(S)g(S) は、集合内の配線数である。全体の回路で SS がちょうど一つの連結成分になるには、内部を連結にし、外部と一本もつながず、残りの端子もすべて配線すればよい。

r(S)=b(S)=mr(S)=b(S)=m なら、外側には赤青の端子がそれぞれ M−mM-m 個残る。外側は何成分に分かれてもよいので、その配線は (M−m)!(M-m)! 通り。従って求める確率は

g(S)(M−m)!M!\frac{g(S)(M-m)!}{M!}

である。赤青の端子数が違う集合の確率は0とする。内部の頂点集合も端子も既に決まっているため、ここで頂点や端子を選ぶ組合せ係数を掛ける必要はない。

非空集合 SS ごとに、実際の回路でその集合がちょうど一つの成分なら1、そうでなければ0となる指示変数 ISI_S を置く。一つの回路を固定すると、1になる集合はその回路の成分の頂点集合だけである。成分数を CC と書けば

C=∑∅≠S⊆VISC=\sum_{\emptyset\neq S\subseteq V}I_S

となる。期待値の線形性と、指示変数の期待値がその事象の確率になることから、

E[C]=∑∅≠S⊆VPr⁡(IS=1)=1M!∑∅≠S⊆Vr(S)=b(S)g(S)(M−r(S))!\begin{aligned} \mathbb{E}[C] &=\sum_{\emptyset\neq S\subseteq V}\Pr(I_S=1)\\ &=\frac{1}{M!} \sum_{\substack{\emptyset\neq S\subseteq V\\r(S)=b(S)}} g(S)(M-r(S))! \end{aligned}

を得る。各集合が成分になる事象は互いに独立でなくてよい。

3頂点の小例では、例えば {1}\{1\} が成分となる確率は 1⋅2!/3!=1/31\cdot 2!/3!=1/3。外側の二頂点の配線を2通りとも数える必要がある。単頂点集合が三つ、二頂点集合が三つ、全体集合が一つなので、期待値は

3⋅1⋅2!3!+3⋅1⋅1!3!+2⋅0!3!=1163\cdot\frac{1\cdot 2!}{3!} +3\cdot\frac{1\cdot 1!}{3!} +\frac{2\cdot 0!}{3!} =\frac{11}{6}

となる。

部分集合DPとしての計算手順

集合を頂点ごとのビットで表し、r(S),b(S),f(S),g(S)r(S),b(S),f(S),g(S) を配列に持つ。計数はすべて法 p=998244353p=998244353 上で行う。

  1. 入力の各端子が属する頂点を数え、rv,bvr_v,b_v を作る。0!0! から M!M! までの階乗も前計算する。
  2. 各集合で含まれる頂点の端子数を足し、r(S),b(S)r(S),b(S) と f(S)f(S) を求める。空集合は何もつながない一通りとして f(∅)=1f(\emptyset)=1、連結成分には使わないので g(∅)=0g(\emptyset)=0 とする。
  3. 非空集合を要素数の昇順で処理する。赤青の端子数が違えば g(S)=0g(S)=0 とする。それ以外では g(S)g(S) を f(S)f(S) で初期化し、最小番号の頂点を aa に選ぶ。a∈T⊊Sa\in T\subsetneq S を満たす部分集合を列挙し、g(T)f(S∖T)g(T)f(S\setminus T) を引く。参照する TT は必ず小さく、その値は既に確定している。
  4. 赤青の端子数が一致する各非空集合について g(S)(M−r(S))!g(S)(M-r(S))! を足し、最後に (M!)−1(M!)^{-1} を一度掛けて出力する。

pp は素数で、M≤105<pM\leq 10^5<p だから M!M! は法 pp で0にならず、逆元が存在する。逆元はフェルマーの小定理から (M!)p−2 mod p(M!)^{p-2}\bmod p を二分累乗で求められる。普通の整数除算で確率を計算してはいけない。

典型の発動条件

indicator期待値

数えたい量を「ある対象が条件を満たせば1、そうでなければ0」の和にできるとき、対象を固定して確率を求める。本問では頂点集合を固定することで、成分数の分布全体を持たずに済む。期待値の線形性に、事象同士の独立性は不要である。

connected構造のsubset DP

集合上の全構造は数えやすいが、連結なものだけ数えたいときに使う。固定頂点を含む成分を切り出し、残りの任意構造と独立に組み合わせられるかを確認する。頂点ごとに端子数が違う本問では、集合の大きさだけでなく、どの頂点を含むかまで状態に残す必要がある。

3^N submask enumeration

各集合に対してその部分集合を走査するときは、一組の集合を構成する各頂点の所属を数える。本問では「選んだ成分」「残り」「元の集合の外」の三択となり、全遷移を O(3N)O(3^N) で評価できる。

問題固有の要素

赤青を一つずつつなぐという条件から、集合内で配線を閉じられる条件が端子数の一致に、閉じる配線数が階乗になる。連結性だけをDPで取り出し、外側も階乗で数えることで、「内部が連結」と「外へ辺が出ない」を同時に満たす確率を得られる。自己ループや多重辺を消したグラフの個数ではなく、区別された端子の対応を数える点が重要である。

正当性

集合内で閉じる配線は、赤青の端子数が異なると存在せず、各色が mm 個なら赤から青への全単射と一対一に対応するため f(S)=m!f(S)=m! 通りである。

非連結な配線には、固定頂点 aa を含む成分の集合 T⊊ST\subsetneq S が一意に存在する。この配線を TT 内の連結な配線と、残りの集合内で閉じる配線へ分ける操作は、両者を合わせる操作と互いに逆である。従って各分類の個数は g(T)f(S∖T)g(T)f(S\setminus T) となり、引き算の漸化式は非連結な配線を漏れなく一度ずつ除く。単頂点集合では引く項がなく、この式を小さい集合から計算すればすべての g(S)g(S) が正しく求まる。

赤青各 mm 端子の非空集合 SS が全体の一成分になる配線は、その内部の連結な配線と、外部の赤青各 M−mM-m 端子を結ぶ任意の配線の組に一対一に対応する。よってその個数は g(S)(M−m)!g(S)(M-m)!。全体の M!M! 通りが等確率であり、各回路の成分数は全非空集合の指示変数の和なので、最終集計は成分数の期待値に等しい。

端子が一つもない集合でも、何もつながない配線は存在するため f(S)=0!=1f(S)=0!=1 である。単頂点なら辺がなくても一つの成分なので g(S)=1g(S)=1。二頂点以上なら連結にできず g(S)=0g(S)=0 になる。また、端子を持つ頂点と持たない頂点が混在する集合も、端子のない頂点が孤立するため g(S)=0g(S)=0 となる。同じ漸化式がこれらの非連結な配線を取り除く。

実装上の注意

  • 引く集合は固定頂点を含む真部分集合だけにする。T=ST=S を含めると、求めたい g(S)g(S) 自身まで引いてしまう。固定頂点を含まない集合も引くと、一つの非連結な配線を複数回引く。
  • 赤青の端子数が違う集合は f(S)=g(S)=0f(S)=g(S)=0 とする。端子数が両方0なら f(S)=0!=1f(S)=0!=1 であり、端子を持たない頂点を状態から除いてはいけない。
  • 部分集合は、整数マスクの昇順で処理してもよい。真部分集合のマスクは必ず元より小さいので、要素数順と同じ依存関係を満たす。
  • 積は法を取る前に符号付き64 bit整数で計算し、引き算後の剰余は非負に正規化する。全項をためず、その都度剰余を取る。

復習の核

  • 「成分数の期待値」では、成分の候補となる頂点集合を固定し、その集合がちょうど一成分になる確率を足す。
  • 全構造から連結構造を取り出すときは、固定頂点を含む成分を一つだけ選ぶ。残りは連結でなくてよい。
  • 内部だけの配線数から全体の確率へ移るには、外側の自由な配線数も掛ける。端子のない孤立頂点も一成分として数える。

計算量と制約

時間

入力の集計と階乗の前計算に O(M+N)O(M+N)、各集合に含まれる頂点を走査して端子数を求める処理に O(N2N)O(N2^N) かかる。要素数ごとの集合の振り分けもこの範囲で行える。

漸化式の全遷移では、各頂点が TT、S∖TS\setminus T、V∖SV\setminus S のいずれかに属する。三択の割り当ては全体で 3N3^N 通りであり、固定頂点の条件や真部分集合の条件は走査数を増やさない。従ってDPは O(3N)O(3^N)、最終集計は O(2N)O(2^N)。逆元の二分累乗は O(log⁡p)O(\log p) で、p=998244353p=998244353 は固定なので、全体は O(3N+N2N+M)O(3^N+N2^N+M) 時間となる。

空間

集合ごとの端子数と f,gf,g、処理順の保持に O(2N)O(2^N)、階乗配列に O(M)O(M)、頂点ごとの端子数に O(N)O(N)。合計 O(2N+M+N)O(2^N+M+N) である。入力の端子列を保存する場合も O(M)O(M) に収まる。

制約との対応

1≤N≤171\leq N\leq 17、1≤M≤1051\leq M\leq 10^5、1≤Ri,Bi≤N1\leq R_i,B_i\leq N。時間制限は3秒、メモリ制限は1024 MiBである。頂点集合の状態数は最大 217=1310722^{17}=131072 で、端子の対応を M!M! 通り列挙する代わりに部分集合DPを使える。三択の全割り当ては 317=1291401633^{17}=129140163 通りであり、固定頂点を含む真部分集合に絞ると実際の減算項はさらに少ない。端子数の偏りを許す制約なので、端子数が不一致の集合と、端子を持たない頂点も扱う。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Electric Circuit の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

    主タグ: label付き連結成分分解・exponential formula

    補助タグ: 組合せ係数・数え上げ 寄与の数え上げと順序交換 法上の四則演算・高速累乗・逆元 部分集合・bitmask状態DP

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

    学習の位置

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

    • 最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題