考察
条件はx_i≤x_{A_i}である。まず各iから親A_iへi→A_iを張る。これなら出次数が1のfunctional graphで、各弱連結成分は一つのcycleとそこへ流れ込む木からなる。cycle上は不等式が一周して全値が等しくなるのでcycleを一つのrootへ縮約する。
木DPでは逆向きのparent→childをたどる。cycleでない各iをchildren[A_i]へ入れ、cycle頂点間の辺だけ除く。cycle rootの子はcycle上の全頂点へ入っていた木の子を集める。この向きでは親値jに対し子値は1..jであり、各子部分木は独立である。
pref_child[j] = Σ_{k=1}^j dp[child][k], pref_child[0]=0
dp[v][j] = ∏_{child c} pref_c[j], 1≤j≤M
componentWays = Σ_{j=1}^M dp[root][j]
answer = 全componentWaysの積
葉では空積なのでdp[v][j]=1。縮約cycle rootにもM通りの共通値jがあり、cycle長だけ値の選択回数を掛けない。postorderで子ごとにprefix sumを一回作れば、一つの辺の全jをO(M)で処理できる。成分ごとのroot値の和を取り、独立な成分間で掛ける。
A=(2,1,1),M=3なら1,2がcycleで値jは等しく、子3には1..jのj通り。従ってΣ_{j=1}^3 j=6。graphをA_i→iで作ってもよいが、その場合は木がcycleから外へ伸びる向きであり、それをさらに反転してDPの子としてはならない。向きの混同を避けるため、ここではcycle検出用i→A_iとDP用A_i→iを明示的に分ける。
典型の発動条件
functional graphのcycle縮約
発動条件: 各頂点が一つの親を持ち、cycle上の制約が全頂点を同値化するとき。
cycleを一頂点としてrooted treeへ変える。
tree DPの累積和高速化
発動条件: 親値に応じて子値のprefix/suffix範囲を合計するとき。
子dpのprefix sumを全jへ使い回す。
問題固有の要素
循環不等式は矛盾でなくcycle全体の等値を強制するので、cycle長を状態へ持つ必要がない。
別の問題へ持ち帰る視点: 有向cycle上に単調な順序制約が閉じている場合、全辺が等号になり縮約できる。
正当性
cycle上の一周の不等式は全値等号を強制するため一頂点へ縮約してよい。親値jを固定すると各子は1..jから独立に選べ、子DP prefix和の積が厳密な部分木数。葉からの帰納法で各rootの和が成分数となり、成分は独立なので積が全答え。 cycle検出ではi→A_i、木DPではその逆の親A_i→子iを用いる。親値jに対するx_i≤jという元の不等式とprefix和の範囲が一致し、逆向きの不等式を数えない。
実装上の注意
- 自己loopもcycleとして一rootにする。縮約後のchild重複を避け、mod積とprefix sumを各mergeで正規化する。
復習の核
- 自己loop、長いcycle、cycle頂点ごとに木が付くN≤8例を全M^N列挙し、縮約前後の条件とcomponent積を照合する。
計算量と制約
時間
N 頂点、選択値上限 M。cycle縮約 O(N)、prefix和DP O(NM)。
空間
全縮約頂点DPを保存するなら O(NM)、グラフO(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, M \leq 2025; 1 \leq A_i \leq N; All input values are integers.
出典