ABC 327 G — Many Good Tuple Problems

考察

各pair(S_i,T_i)をlabel iのdirected edgeと見ると、条件を満たす0/1頂点彩色が存在することはunderlying multigraphがbipartiteであることと同値である。

bipartite multigraphにはloopがなく、各undirected labeled edgeの向きが2通りなので、原問題の答えはundirected edge-labeled bipartite multigraph数a(N,M)の2^M倍になる。

parallel edgeを1本へ潰したsupportがk-edge simple bipartite graphなら、M labeled edgeをk support edgeへsurjectiveに割り当てる通り数b(M,k)だけ元multigraphが対応する。

採用する候補: simple bipartite graphをedge数別にconnected-component DPで数え、surjection数を掛けてmultigraphへ戻す。

巨大Mはi^Mの高速冪だけへ閉じ込め、N≤30のsimple support edge上限L≤225で全計数を行える。

棄却する候補: 頂点の2-coloringを選びcross edge列を数えて全coloring数で割る。

同じdisconnected bipartite graphのvalid coloring数はcomponent数で変わり、一律な係数では重複を除けない。

棄却する候補: N^{2M}個のendpoint sequence pairを列挙してbipartite判定する。

Mが10^9で列挙不能である。

colored simple bipartite graph数はg(n,m)=Σ_{i=0}^n C(n,i)C(i(n-i),m)で、i black・n-i white間のedgeを選ぶ。

anchor頂点を含むconnected componentで分ける除原理により、colored connected数hをgから抽出し、connected uncolored bipartite graph数はh/2になる。

uncolored graph fはconnected componentをanchor付きで組み立て直し、最後にa(N,M)=Σ_k f(N,k)b(M,k)とする。

L=floor(N/2)ceil(N/2)までbinomialを前計算しg(n,m)を作る。h(n,m)=g(n,m)−Σ_{i<n,j}C(n-1,i-1)h(i,j)g(n-i,m-j)でcolored connected数を求め、c=h/2とする。f(0,0)=1から、vertex 1を含むconnected componentを選ぶ標準漸化式f(n,m)=Σ_{i=1..n,j}C(n-1,i-1)c(i,j)f(n-i,m-j)でsimple bipartite graphを数える。b(M,k)=Σ_{i=0}^k(-1)^{k-i}C(k,i)i^Mを求め、2^MΣ_{k=0}^L f(N,k)b(M,k)を出力する。

典型の発動条件

multigraphのsimple support化

発動条件: parallel edgeを許すlabel付きgraphを数え、異なるedge種類数が小さいとき。

support graphとedge labelのsurjectionへ分解する。

connected構造の除原理DP

発動条件: 全labelled構造gからconnected構造hを抽出し、再びcomponent集合を組み立てたいとき。

anchor vertexのcomponentを固定してconvolutionする。

surjectionの包含排除

発動条件: M labeled要素をk個の箱すべてへ少なくとも1個入れるとき。

Σ(-1)^{k-i}C(k,i)i^Mで数える。

proper coloringの重複補正

発動条件: connected bipartite graphをproper 2-coloring付きで数えたとき。

connectedならcolor swapの2通りなので2で割る。

問題固有の要素

Mが巨大でも、bipartite simple supportのedge種類数は最大floor(N²/4)なので、M依存はsupport edgeへのsurjectionだけに分離できる。

別の問題へ持ち帰る視点: 巨大個数の反復要素を持つ構造は、distinct supportとlabel付きmultiplicity割当へ分けると小dimension DP+高速冪になる。

正当性

tupleの制約はunderlying graphが二部であることと同値。supportの各辺へM本のlabel付き辺を全射割当てする数をb(M,k)とすれば、同supportの多重辺を正確に復元できる。彩色二部graphからanchor成分でconnected数を抽出し、その2色交換の倍率2を除くとuncolored connected数になる。再び成分を組立て、各辺の向き2^Mを戻せば全tupleを一度数える。

実装上の注意

  • singleton zero-edge componentではh(1,0)=2、c(1,0)=1となるため、m=0をDP tableから落とさない。
  • fのcomponent recurrenceはvertex 1を含むconnected componentを一意に選び、binomial係数とi,n-iの向きを揃える。
  • M≥1なのでb(M,0)=0とし、包含排除の負値とinv2をmod 998244353で正規化する。

復習の核

  • N=3,m=0でempty graphがf=1になるcomponent recurrenceと、1本edge supportへM labeled parallel edgeを割り当てるb(M,1)=1を確認する。

計算量と制約

時間

O(N²E²+E² log M)を上界とする。E=⌊N²/4⌋、成分DPを辺数ごとに素朴合成する。

空間

O(NE)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 30; 1 \leq M \leq 10^9; N and M are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Many Good Tuple Problems の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

    補助タグ: 二部グラフの彩色と成分構造 組合せ係数・数え上げ 集合上の包除原理 法上の四則演算・高速累乗・逆元

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

    学習の位置

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

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

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題