ABC 336 G — 16 Integers
分類・前提・執筆情報
掲載状態: 収録済み
最終確認:
学習上の位置付け
主題の単元: BEST定理によるEuler circuit数え上げ
- 主題
- BEST定理によるEuler circuit数え上げ: 有向Euler graphのcircuit数をrooted arborescenceの行列式と各頂点の出辺順列へ分解して数える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
- 追加で学ぶ技能
- 既習技能
- Euler trail・circuit: 無向graphでは辺を持つ部分の連結性と奇数次数頂点数が0または2であることを調べ、有向graphでは辺を持つ部分の弱連結性と入次数・出次数の差(trailなら始点+1、終点−1、他0、circuitなら全頂点0)を調べ、全辺を一度ずつ使うtrail・circuitの存在を判定できる。
- 法上の四則演算・高速累乗・逆元: 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。
- 行列式による数え上げ: 辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。
- 組合せ係数と対称性で数える: 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。
主タグ: BEST定理によるEuler circuit数え上げ
補助タグ: 組合せ係数・数え上げ 行列式による数え上げ Euler trail・circuit 法上の四則演算・高速累乗・逆元
執筆: abc-explanation-author1.1.1 / revision 1
学習の位置
体系上の位置: BEST定理によるEuler circuit数え上げ
- 有向Euler graphのcircuit数をrooted arborescenceの行列式と各頂点の出辺順列へ分解して数える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
先に読む単元:
- 組合せ係数と対称性で数える — 選び方を通常・Gaussian二項係数で整理し、必要ならStirling変換でrank別計数を基底変換する。
- 行列式による数え上げ — 線形方程式・rankで得た考え方と実装を再利用し、行列式による数え上げの発動条件・正当化・境界を重複なく学ぶ。
- Euler trail・circuit — 全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
- 法上の四則演算・高速累乗・逆元 — 剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る