ABC 310 G — Takahashi And Pass-The-Ball Game

考察

一回の移動写像Aは、ベクトルvに対して(A v)_j=Σ_{i:A_i=j}v_iという分布移動を表す。求めるのは一回移動後の分布bから始まるΣ_{t=0}^{K−1}A^t bをKで割った期待値である。

長さℓのblockに対してS=A^ℓ、x=Σ_{t=0}^{ℓ−1}A^t bを一組にする。倍化はx'=x+Sx、S'=S∘S。写像適用は各iのv_iをS_iへ足すだけで、写像合成もS'_i=S_{S_i}なので両方O(N)である。

Kのbitを下から見て、S=A,x=b, F=恒等写像, ans=0から始める。F=A^pは既に取り込んだp時刻の直後への写像。現在bitが1ならans←ans+F x、F←S∘Fとしてblockを時刻pの後ろへ足す。その後、古いS,xからx←x+Sx、S←S∘Sを別bufferで同時更新する。例えばK=3ではbを取り込み、二倍block(b+Ab)をAで移して、b+Ab+A²bを得る。

全bitを処理したらansをKの法上の逆元で割る。各頂点のボールは合流しても分布ベクトルの加算に吸収されるので、行列N×Nを作る必要はない。

典型の発動条件

作用と区間和のダブリング

発動条件: 同じ写像を巨大回数適用した途中状態の総和も必要なとき。

2^b 回後の写像と、その 2^b 区間での寄与を対にして合成する。

functional graph 上の線形輸送

発動条件: 各要素の遷移先が一意で、重みが遷移先へ合算されるとき。

写像配列を使ってベクトルを gather し、写像同士も添字参照で合成する。

問題固有の要素

最終状態ではなく全時刻平均なので、通常の doubling table に「区間中に何を足したか」を持たせる。

別の問題へ持ち帰る視点: 巨大反復の累積量は、遷移モノイドを作用付きの pair へ拡張すると二分累乗できる。

正当性

写像適用はボール移動と等しく線形である。blockの不変条件S=A^ℓ,x=Σ_{t<ℓ}A^t bは、後半がSxになる倍化で保たれる。答え側の不変条件F=A^p,ans=Σ_{t<p}A^t bは、F xを加えてFをS∘Fへ更新すればℓ時刻延ばされる。Kのbitの和でp=Kになり、一回操作後1,…,K時刻の分布を全て一度加える。Kで割れば一様な操作回数の期待分布になる。

実装上の注意

  • xとSの倍化は古い値から計算し、移動先への加算を新bufferへ行う。in-place更新では合流やcycleが混ざる。
  • 答えにblockを取り込むときはF xを足し、時刻offsetの写像Fも更新する。
  • bは一回操作後、blockは0,…,K−1回の追加操作を表す。入力制約でKの逆元が存在することを確認する。

復習の核

  • 反復過程の平均を見たら、まず求める時刻列を明記して和へ直す。次に「2倍区間の後半は前半へ写像を一度作用させたもの」と捉える。

計算量と制約

時間

N 頂点、時刻上限 K。写像適用と倍化が各 O(N) なので O(N log K)。

空間

現在写像と区間和ベクトルだけなら O(N)、全段保存なら O(N log K)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 2\times10^5; 1\leq K\leq 10^{18}; K is not a multiple of 998244353.; 1\leq A _ i\leq N\ (1\leq i\leq N); 0\leq B _ i\lt998244353\ (1\leq i\leq N); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Takahashi And Pass-The-Ball Game の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: doubling・binary lifting

主題
  • doubling・binary lifting: 一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: doubling・binary lifting

    補助タグ: 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: doubling・binary lifting

    • 一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題