考察
連結成分数を直接追う代わりに、「どの頂点集合が一つの成分になるか」を数える。集合内で閉じる配線は簡単に数えられるので、そこから非連結な配線を引いて、連結な配線を求めよう。固定した一頂点を含む成分に注目すると、引く対象を重複なく分けられる。
端子の対応を、頂点集合ごとに数える
部品を頂点、ケーブルを無向辺とみなす。同じ部品の赤青端子をつなぐ自己ループや、同じ二部品を結ぶ複数の辺も許される。端子は一つずつ区別するが、ケーブル同士は区別しない。赤い端子を順に見て、接続先の青い端子を一つずつ割り当てると、全体の配線は 通りになる。同じグラフになっても、端子の対応が違えば別の配線である。
すべての配線を作って成分数を数える方法は、 では使えない。一方、頂点数は と小さい。そこで、端子の対応そのものではなく、頂点の部分集合を状態にする。
全頂点集合を とする。頂点 の赤い端子数を 、青い端子数を とし、部分集合 内の端子数を
と定める。まず を、集合内の全端子を使い、外へ一本も出さずに閉じる配線の数とする。各ケーブルは赤青を一つずつ使うため、両色の端子数が違えば閉じられない。一致して 個ずつなら、青い端子の割り当て方を数えればよい。
次に、非空集合 に対して を、集合内で閉じ、かつ 全体が連結になる配線の数とする。 は複数の成分に分かれる配線も含むが、 は含まない。赤青の端子数が違う場合は でもある。
違いを見る独自の小例として、頂点1、2のそれぞれに赤青の端子が一つずつある場合を考える。集合 内の配線は次の2通りだ。
- 各頂点で赤青をつなぐ。自己ループが一つずつでき、成分は と に分かれる。
- 頂点1の赤と頂点2の青、頂点2の赤と頂点1の青をつなぐ。二頂点が連結になる。
従って だが、 である。「外へ出ない」だけでは、一つの成分とは限らない。
固定頂点を含む成分で、非連結な配線を一度ずつ引く
連結性を満たす配線を直接作るより、数えやすい から非連結なものを引きたい。しかし「連結な部分を一つ選ぶ」だけでは、一つの配線から複数の成分を選べてしまう。そこで の頂点を一つ固定し、それを含む成分だけを選ぶ。
先ほどの例を3頂点へ広げ、各頂点に赤青の端子を一つずつ置く。 とし、頂点1を固定する。非連結な配線で、頂点1を含む成分の頂点集合を とすると、候補は次の三つになる。
一行目の残り二頂点は、互いにつながっても、自己ループだけで別々になってもよい。そのため残りには ではなく を使う。全頂点に自己ループがある配線も、頂点1の成分は に一意に決まるので、一行目で一度だけ引かれる。
全配線は 通りだから、連結な配線は 通りとなる。これは三頂点を一周する、赤から青への二つの対応に当たる。
一般にも、非空集合 の固定頂点を とする。非連結な配線を、 を含む成分の頂点集合 で分類する。 は を含む真部分集合であり、成分内は 通り、残りは 通りで独立に選べる。従って
となる。どの配線でも の属する成分は一つだけなので、各非連結な配線はちょうど一度引かれる。小さい集合の が分かれば、より大きい集合の を求められる。
一つの成分になる確率から、期待値へ戻す
ここまでの は、集合内の配線数である。全体の回路で がちょうど一つの連結成分になるには、内部を連結にし、外部と一本もつながず、残りの端子もすべて配線すればよい。
なら、外側には赤青の端子がそれぞれ 個残る。外側は何成分に分かれてもよいので、その配線は 通り。従って求める確率は
である。赤青の端子数が違う集合の確率は0とする。内部の頂点集合も端子も既に決まっているため、ここで頂点や端子を選ぶ組合せ係数を掛ける必要はない。
非空集合 ごとに、実際の回路でその集合がちょうど一つの成分なら1、そうでなければ0となる指示変数 を置く。一つの回路を固定すると、1になる集合はその回路の成分の頂点集合だけである。成分数を と書けば
となる。期待値の線形性と、指示変数の期待値がその事象の確率になることから、
を得る。各集合が成分になる事象は互いに独立でなくてよい。
3頂点の小例では、例えば が成分となる確率は 。外側の二頂点の配線を2通りとも数える必要がある。単頂点集合が三つ、二頂点集合が三つ、全体集合が一つなので、期待値は
となる。
部分集合DPとしての計算手順
集合を頂点ごとのビットで表し、 を配列に持つ。計数はすべて法 上で行う。
- 入力の各端子が属する頂点を数え、 を作る。 から までの階乗も前計算する。
- 各集合で含まれる頂点の端子数を足し、 と を求める。空集合は何もつながない一通りとして 、連結成分には使わないので とする。
- 非空集合を要素数の昇順で処理する。赤青の端子数が違えば とする。それ以外では を で初期化し、最小番号の頂点を に選ぶ。 を満たす部分集合を列挙し、 を引く。参照する は必ず小さく、その値は既に確定している。
- 赤青の端子数が一致する各非空集合について を足し、最後に を一度掛けて出力する。
は素数で、 だから は法 で0にならず、逆元が存在する。逆元はフェルマーの小定理から を二分累乗で求められる。普通の整数除算で確率を計算してはいけない。
典型の発動条件
indicator期待値
数えたい量を「ある対象が条件を満たせば1、そうでなければ0」の和にできるとき、対象を固定して確率を求める。本問では頂点集合を固定することで、成分数の分布全体を持たずに済む。期待値の線形性に、事象同士の独立性は不要である。
connected構造のsubset DP
集合上の全構造は数えやすいが、連結なものだけ数えたいときに使う。固定頂点を含む成分を切り出し、残りの任意構造と独立に組み合わせられるかを確認する。頂点ごとに端子数が違う本問では、集合の大きさだけでなく、どの頂点を含むかまで状態に残す必要がある。
3^N submask enumeration
各集合に対してその部分集合を走査するときは、一組の集合を構成する各頂点の所属を数える。本問では「選んだ成分」「残り」「元の集合の外」の三択となり、全遷移を で評価できる。
問題固有の要素
赤青を一つずつつなぐという条件から、集合内で配線を閉じられる条件が端子数の一致に、閉じる配線数が階乗になる。連結性だけをDPで取り出し、外側も階乗で数えることで、「内部が連結」と「外へ辺が出ない」を同時に満たす確率を得られる。自己ループや多重辺を消したグラフの個数ではなく、区別された端子の対応を数える点が重要である。
正当性
集合内で閉じる配線は、赤青の端子数が異なると存在せず、各色が 個なら赤から青への全単射と一対一に対応するため 通りである。
非連結な配線には、固定頂点 を含む成分の集合 が一意に存在する。この配線を 内の連結な配線と、残りの集合内で閉じる配線へ分ける操作は、両者を合わせる操作と互いに逆である。従って各分類の個数は となり、引き算の漸化式は非連結な配線を漏れなく一度ずつ除く。単頂点集合では引く項がなく、この式を小さい集合から計算すればすべての が正しく求まる。
赤青各 端子の非空集合 が全体の一成分になる配線は、その内部の連結な配線と、外部の赤青各 端子を結ぶ任意の配線の組に一対一に対応する。よってその個数は 。全体の 通りが等確率であり、各回路の成分数は全非空集合の指示変数の和なので、最終集計は成分数の期待値に等しい。
端子が一つもない集合でも、何もつながない配線は存在するため である。単頂点なら辺がなくても一つの成分なので 。二頂点以上なら連結にできず になる。また、端子を持つ頂点と持たない頂点が混在する集合も、端子のない頂点が孤立するため となる。同じ漸化式がこれらの非連結な配線を取り除く。
実装上の注意
- 引く集合は固定頂点を含む真部分集合だけにする。 を含めると、求めたい 自身まで引いてしまう。固定頂点を含まない集合も引くと、一つの非連結な配線を複数回引く。
- 赤青の端子数が違う集合は とする。端子数が両方0なら であり、端子を持たない頂点を状態から除いてはいけない。
- 部分集合は、整数マスクの昇順で処理してもよい。真部分集合のマスクは必ず元より小さいので、要素数順と同じ依存関係を満たす。
- 積は法を取る前に符号付き64 bit整数で計算し、引き算後の剰余は非負に正規化する。全項をためず、その都度剰余を取る。
復習の核
- 「成分数の期待値」では、成分の候補となる頂点集合を固定し、その集合がちょうど一成分になる確率を足す。
- 全構造から連結構造を取り出すときは、固定頂点を含む成分を一つだけ選ぶ。残りは連結でなくてよい。
- 内部だけの配線数から全体の確率へ移るには、外側の自由な配線数も掛ける。端子のない孤立頂点も一成分として数える。
計算量と制約
時間
入力の集計と階乗の前計算に 、各集合に含まれる頂点を走査して端子数を求める処理に かかる。要素数ごとの集合の振り分けもこの範囲で行える。
漸化式の全遷移では、各頂点が 、、 のいずれかに属する。三択の割り当ては全体で 通りであり、固定頂点の条件や真部分集合の条件は走査数を増やさない。従ってDPは 、最終集計は 。逆元の二分累乗は で、 は固定なので、全体は 時間となる。
空間
集合ごとの端子数と 、処理順の保持に 、階乗配列に 、頂点ごとの端子数に 。合計 である。入力の端子列を保存する場合も に収まる。
制約との対応
、、。時間制限は3秒、メモリ制限は1024 MiBである。頂点集合の状態数は最大 で、端子の対応を 通り列挙する代わりに部分集合DPを使える。三択の全割り当ては 通りであり、固定頂点を含む真部分集合に絞ると実際の減算項はさらに少ない。端子数の偏りを許す制約なので、端子数が不一致の集合と、端子を持たない頂点も扱う。
出典