ABC 309 Ex — Simple Path Counting Problem

考察

高さ 1..M の単純路を一段進む遷移は、位置を −1,0,+1 だけ動かす線形作用である。N は 10^9 なので段数 DP はできない一方、幅 M は 10^5 に収まる。

端 0 と M+1 から外へ出る歩道を排除する境界条件だけが平行移動不変性を壊しており、鏡像の負符号でその寄与を相殺できる。

採用する候補: 長さ 2M+2 の符号付き鏡像列へ拡張し、循環畳み込み (x^{-1}+1+x)^{N−1} を高速累乗する。

境界を鏡像で吸収すると各段が同じ巡回畳み込みになり、NTT と二乗法で O(M log M log N) にできる。

棄却する候補: M 状態の遷移行列を二乗して N−1 段をまとめる。

疎行列でも二乗後は密になり、M=10^5 に対する行列積・保持は不可能である。

開始分布を位置 j に正、鏡位置 2M+2−j に負で置くと、禁止境界を越えて戻る経路が一対一に逆符号で対応して消える。

巡回添字を x^{2M+2}=1 とみなせば、一段の遷移は多項式への (x^{-1}+1+x) の乗算そのものになる。

長さ D=2M+2 の f を作り、各開始 A_i の係数を +1、D−A_i を −1 とする。環 Z[x]/(x^D−1) で g=x^{-1}+1+x を N−1 乗し f と畳み込み、B_i の係数を合計する。各積は NTT 後に次数を D 周期で折り返す。

典型の発動条件

鏡像法による境界条件の除去

発動条件: 一様なランダムウォーク・格子路で、壁だけが畳み込み構造を妨げるとき。

反射位置へ逆符号の初期値を置き、壁越え経路を相殺する。

多項式遷移の高速累乗

発動条件: 巨大な反復回数に対し、一段の線形遷移が平行移動不変な小 kernel で表せるとき。

状態列を多項式とみなし、商環上で kernel を二分累乗する。

問題固有の要素

鏡像法は確率の閉形式だけでなく、有限区間 DP を巡回畳み込みへ変換するためにも使える。

別の問題へ持ち帰る視点: 巨大な時間軸と中程度の空間軸を見たら、境界を処理して遷移を convolution にできないか検討する。

正当性

開始分布を鏡位置へ逆符号で置くと、反射対称な移動作用のもと境界0,M+1の係数は常に0である。内部では隣接・停止の通常遷移と一致するため、内部係数は外へ出ない経路数のDPを満たす。周期環でN−1乗してもこの不変条件を保ち、終点分布との内積で全指定開始終点の経路を数える。

実装上の注意

  • x^{-1} は配列添字 D−1 に置き、畳み込み後の次数を D で正しく折り返す。負係数を法で正規化し、問題文の B の重複もそのまま加算する。

復習の核

  • 巨大回数の DP ではまず一段作用が線形かを見る。その後、境界だけを切り離し、鏡像で translation invariant に戻せるかを追う。

計算量と制約

時間

O(M log M·log N+K+L)。周期長D=2M+2の積をNTTで累乗する。

空間

O(M+K+L)。

制約との対応

公式制約の確認範囲: Time limit: 10 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 10^9; 1 \le M,K,L \le 10^5; 1 \le A_i,B_j \le M

出典

分類・前提・執筆情報

掲載状態: 収録済み

Simple Path Counting Problem の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 鏡像法・reflection principle

主題
  • 鏡像法・reflection principle: 最初に境界を破るpathとの鏡像対応を構成し、壁付きwalkの数え上げを符号付きの無境界問題へ変換できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 鏡像法・reflection principle

    補助タグ: 畳み込み・相互相関

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

    学習の位置

    体系上の位置: 鏡像法・reflection principle

    • 最初に境界を破るpathとの鏡像対応を構成し、壁付きwalkの数え上げを符号付きの無境界問題へ変換できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題