ABC 336 G — 16 Integers

考察

長さ4のpattern(i,j,k,l)を、3bit状態(i,j,k)から(j,k,l)への有向辺と見る。各pattern出現回数Xはその多重辺数であり、条件を満たすbinary列は全辺を一度ずつ使うEuler trailと一対一対応する。

採用する候補: 8頂点多重有向graphのEuler trailをBEST定理と有向行列木定理で数える

辺総数Nが大きくても頂点数は8に固定され、degree・factorial・小行列式だけで計算できる。

棄却する候補: 16種類のpatternを置く順序をDPで列挙する

残個数vectorの状態数がXに対して指数的で、N=10^6を扱えない。

始点・終点候補を8通りずつ調べ、degree差がEuler trail条件を満たす場合は終点から始点への補助辺を加えてEuler閉路へ帰着できる。区別された辺の閉路数はBEST定理の有向全域木数×∏(outdeg(v)-1)!で、全域木数は有向Laplacian minorの行列式になる。

各始点s・終点tのdegree条件を調べ、辺を持つ頂点とs,tだけをVとする。元の辺と区別する補助辺e*:t→sをs=tでも一個加え、V上の連結性と入出次数一致を確認する。e*を最初の辺に固定した閉路からe*を切ると、sからtへの線形なtrailと一対一対応する。自己ループを除いたV上の有向Laplacianから根tの行・列を除き、その余因子の行列式を求める。一頂点なら空行列式は1。これに補助辺・自己ループを含む次数の∏(outdeg(v)-1)!を掛け、元の16種類のX_e!だけで割り、始終点について合計する。X0000=1だけなら答えは1であり、未使用の7頂点を行列へ残してはいけない。

典型の発動条件

de Bruijn graphへの変換

発動条件: 固定長substringの出現回数を指定された列を数える。

長さ3のprefix/suffixを頂点、長さ4 patternをshift辺として、列をEuler trailに対応させる。

BEST定理と有向行列木定理

発動条件: 頂点数が小さい多重有向graphで全辺を使うtrail数が必要である。

edge順序のfactorial積とLaplacian minor determinantからEuler閉路数を得る。

問題固有の要素

同じ4bit patternの辺は列から区別できないため、区別辺に対するBESTの数を各X_e!で割る正規化が必要である。

別の問題へ持ち帰る視点: substring頻度列挙ではEuler路化に加え、同label多重辺のindistinguishabilityをfactorialで補正する。

正当性

各長さ4patternは重なる長さ3状態間の辺なので、binary列とpattern全数を使うEuler trailが全単射。degree条件を満たす始終点へ補助辺t→sを加え、その辺を先頭に固定して閉路を切れば線形trailを一度得る。BESTのarborescence数と次数階乗が区別辺の順序を数え、元pattern別X!を除くと同じ文字列の平行辺ラベル差を除ける。

実装上の注意

  • 辺が存在する頂点だけの連結性と、s=tのEuler circuit caseを分岐する。self-loopはdegreeとfactorialには含めるがarborescence用Laplacianでは適切に除外し、0!を1とする。

復習の核

  • Nの小さい全binary列を列挙し、全辺がself-loop、open trail、closed trail、degree不整合、同pattern多重辺を公式計数と比較する。

計算量と制約

時間

O(L+8³·8²)、L=ΣX≤10^6。階乗前計算と固定サイズ行列木の全始終点。

空間

O(L+8²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: X_{i, j, k, l} are all non-negative integers.; 1 \leq \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l} \leq 10^6

出典

分類・前提・執筆情報

掲載状態: 収録済み

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法で構成する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 法上の四則演算・高速累乗・逆元 — 剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題