label付き連結成分分解・exponential formula
概要
最小ラベルを含む連結成分を一意に切り出し、全構造と連結な構造の個数を結び付ける。ラベル集合をサイズだけで扱えるなら指数型母関数へ、扱えないなら部分集合DPへ進む。
考え方
全体を直接数えにくくても、「一つの連結成分」と「残り」を独立に選べるなら、成分ごとの数え上げへ分解できる。ただし、どの成分を最初に選ぶか自由にすると同じ構造を何度も数えてしまう。最小ラベルを含む成分に固定すると、切り出す成分が一つに決まる。
以下では固定された 個のラベル上の全構造数を 、連結な構造数を とする。同じサイズならラベル集合によらず同じ個数であり、各構造が連結成分の集合へ一意に分かれ、成分間の制約なく合成できる場合を扱う。空構造は一通りなので 、空の連結成分は存在しないので とする。
最小ラベルのある成分を固定する
独自の小例として、ラベル 上の全単純無向グラフを数える。辺の候補は の三つで、それぞれ使うか使わないか選べるから 。連結にするには辺が2本以上必要であり、2本を選ぶ三通りと、3本すべてを使う一通りから となる。単頂点は辺がなくても連結なので 、二頂点ではその間の辺が必要なので である。
8個をラベル1の属する成分で分類する。その成分の頂点集合を 、サイズを とすると、次の表になる。成分から外へ出る辺はすべて使わず、残りの頂点間の辺だけを自由に選ぶ。
| の候補 | 合計 | |||
|---|---|---|---|---|
| 1 | 1 | 2 | 2 | |
| 2 | または | 各1 | 各1 | 2 |
| 3 | 4 | 1 | 4 |
一行目では、残りの辺 を使っても使わなくてもよい。残り全体が連結である必要はないため、ここに使うのは でなく である。二行目では成分のラベル集合が二通りある。三行目の残りは空集合だが、何も作らない一通りとして を掛ける。こうして となり、逆に とも求められる。
一般に、ラベル1を含む成分のサイズを とすると、残りの ラベルの選び方は 通りである。その集合上で 通りの成分を作り、残ったラベル上で 通りの構造を作るので、
を得る。各構造のラベル1の成分は一意であり、逆に選んだ成分と残りを合わせれば元の構造を復元できる。この対応により漏れも重複もない。小例のサイズ2の係数は に当たる。
全構造数が先に分かる場合、 の項が なので、
として の順に復元できる。
指数型生成関数とsubset再帰
このラベル分配を階乗で正規化すると、前単元のEGFの積へつながる。
と置く。漸化式を で割ると、各項は と の積になる。これは形式微分した級数の 係数の比較であり、 を表す。初期値 と合わせて 、逆に となる。
同じ式を成分の集合からも導ける。 個の成分を順序付きで並べるとEGFは となる。それぞれの成分は非空で互いに異なるラベル集合を持つため、同じ成分集合に対応する並べ方はちょうど 通りある。順序を忘れて全成分数を足すと
を得る。 の項は空構造の1である。
先ほどのグラフでは、低次の項は
となる。 へ寄与するのは成分数1、2、3の項だけである。2成分の場合、サイズ1と2を並べる順序は二通りある。従って となり、順序を忘れるため で割ると を得る。三つの成分数からの寄与を足すと、
これは通常の係数であり、個数へ戻すには を掛ける。各項はそれぞれ、連結グラフ4個、辺が1本だけのグラフ3個、辺のないグラフ1個に対応し、合計は となる。ここでの分類は成分数による であり、前の表のラベル1の成分サイズによる とは分類の軸が違う。同じ8個を二通りの一意な分解で数えている。
成分数を変数 の次数でも記録すれば 、成分数がちょうど の構造のEGFは である。個数を取り出すときは、ここでも を使う。
一方、使える辺がラベルごとに違うと、サイズだけでは情報を失う。例えば、辺を だけに制限したパスの部分グラフを考える。同じ二頂点集合でも、 上の連結グラフは1個、 上では0個であり、全グラフ数もそれぞれ2個と1個になる。サイズ2の共通の値 は定められない。
この場合は、頂点集合そのものを状態に持つ。集合 上の全構造数を 、連結構造数を とする。 とし、非空集合について
と分解する。二項係数でラベル集合の選択をまとめる代わりに、各 を直接列挙して、それぞれの内部構造数を使う。パスの全体集合では、ラベル1の成分が となる場合が順に 通りなので、合計は となる。
が既知なら、 の項を移して を求める。真部分集合の値だけを参照するので、集合サイズの昇順で計算すればよい。ABC213 Gでは、入力グラフで使える辺が頂点集合ごとに違うため、この部分集合DPが必要になる。
符号付きの連結グラフへ特殊化する
上の分解は個数だけでなく、成分ごとに積となる重み和にも使える。単純グラフの重みを とすると、全グラフの重み和 は 、 では0になる。一つの辺の候補を固定し、その有無を反転すると、グラフが逆符号の対になって相殺するためである。
連結グラフの符号和を とすれば、最小ラベルの成分を固定した式は、 について
となる。補集合サイズが2以上の項は消え、 だけが残る。 から
を得る。
ABC236 Exでは、等値条件として選んだ辺の成分 ごとに、共通値を 通り選べる。そこで を集合分割の重みとして使う。空分割の重みを とし、非空集合では最小ラベルを含む を列挙して
とする。 も含めるので、全体が一成分の項も空集合の基底から生成できる。成分内部の相殺を導くことと、分割を重複なく合成することは別々に確認する。
成立条件と計算量
サイズだけの漸化式は、必要な二項係数と全構造数が得られていれば、次数 まで 時間で計算できる。二項係数を表で前計算する場合は、その構築も 時間・空間である。階乗と逆階乗を使える場合は、係数を必要時に求め、配列を 空間にできる。
部分集合の再帰をすべての について直接評価すると、 時間・ 空間になる。各ラベルの所属は「 内・ 内・ 外」の三通りであり、最小ラベルの制限を付けてもこの上界に収まる。いずれも や 、成分重みを用意する費用は別途加える。 で高速化する場合の費用はFPS演算に依存する。
EGFによる計算では階乗や整数による除算が必要なので、素数法 なら必要な次数が 未満か確認する。 が可逆でない法でも、二項係数を用いた整数の漸化式自体は成立する。空集合は一通りの構造として扱う一方、連結成分にはしない。
また、成分間の辺・順序・相互制約を別に選ぶ必要がある場合は、 をそのまま使えない。グラフの例では異なる成分間の辺はすべて「使わない」と一意に決まっていた。成分数制約なら を追加するように、何を独立に選べるのかを先に確認する。復習では、最小ラベルで切り出す成分を一意にし、同サイズのラベル集合を同じ個数として扱えるか確かめることを核にする。
問題一覧
- ABC213 G「Connectivity 2」 公式問題組合せ: 部分集合・bitmask状態DP
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 部分集合・bitmask状態DP
- ABC321 G「Electric Circuit」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、部分集合・bitmask状態DP
- ABC318 Ex「Count Strong Test Cases」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。追加で学ぶ技能: FPS基本演算と多項式の多点評価を行う(定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。)。既習技能: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。)。主タグ: 形式的べき級数の基本演算、label付き連結成分分解・exponential formula / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化
- ABC386 G「Many MST」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。追加で学ぶ技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 寄与の数え上げと順序交換、label付き連結成分分解・exponential formula / 補助タグ: 組合せ係数・数え上げ
- ABC327 G「Many Good Tuple Problems」 公式問題
技能・出典
主題: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。既習技能: 二部彩色と成分構造を扱う(連結二部グラフの二つの彩色が部の交換だけで対応することを使い、彩色付きの計数から同じグラフの重複を補正できる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: label付き連結成分分解・exponential formula / 補助タグ: 二部グラフの彩色と成分構造、組合せ係数・数え上げ、集合上の包除原理、法上の四則演算・高速累乗・逆元
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC236 Ex「Distinct Multiples」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。主タグ: 集合上の包除原理 / 補助タグ: label付き連結成分分解・exponential formula
- ABC253 Ex「We Love Forest」 公式問題主題: 行列式による数え上げ
技能・出典
主題: 行列式による数え上げ(辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / label付き連結成分分解・exponential formula(最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。)。主タグ: 行列式による数え上げ / 補助タグ: label付き連結成分分解・exponential formula、法上の四則演算・高速累乗・逆元
前提・学習成果・出典
習得対象の目安: 黄色(2000–2399)。根を含む成分や成分集合の一意な分解から、指数型母関数やsubset再帰を立てる。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-labeled-component-decomposition
label付き連結成分分解・exponential formula
習得する技能
- 最小labelを含む成分を一意に切り出し、全構造とconnected構造の関係をsubset DPまたは指数型母関数で解ける。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 組合せを生成関数へ符号化する。
このUnitを直接前提とする単元: なし。
生成関数による組合せ構造の符号化で得た考え方と実装を再利用し、label付き連結成分分解・exponential formulaの発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- label付き連結成分分解・exponential formulaの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。
根拠
3ラベル上の全単純グラフの分類、EGFの低次展開、パスとの比較は本単元の独自例である。部分集合による成分分解はABC213 G、符号和の利用はABC236 Exの公式解説と照合した。