ABC 450 G — Random Subtraction

考察

操作を展開すると最終xはΣc_iA_i、c_i∈{±1}となる。xの分布全体を求める代わりに、要求されたx²を展開して、どの相関が必要かを見る。

x² = ΣA_i² + 2Σ_{i<j} c_i c_j A_iA_j

対角はc_i²=1で確定する。選ぶ添字に関する操作の対称性により、相異なる全pairの相関e_N=E[c_i c_j]は共通でNだけに依存する。Σ_{i<j}A_iA_j=((ΣA_i)²−ΣA_i²)/2なので、入力からは総和と二乗和だけを集計すれば足りる。

C_N=C(N,2)e_Nを相関の全pair和とし、最初に二要素a,bをa−bへ併合する場合で分ける。小さいN−1要素問題で合成要素に掛かる符号をdとすると、元の二係数はd,−d。そのpairの寄与は−1、外の一要素cとの二pairの和はdc+(−d)c=0である。残る外部N−2要素同士は、N−1要素問題の共通相関e_{N−1}を持つ。従ってN≥3では

C_N = −1 + C(N−2,2)e_{N−1}
    = −1 + (N−3)/(N−1) C_{N−1}

となる。係数(N−3)/(N−1)は、残るpair数C(N−2,2)を小問題の全pair数C(N−1,2)で割った比である。N=1ではC_1=0、N=2では二符号が逆なのでC_2=−1を直接の基底とする。

1..Nの逆元を前計算し、CをNまで順に更新する。N≥2ではe_N=C_N/C(N,2)を取り、答えはsumSq+e_N(sum²−sumSq)。N=1ではA_1²を返す。法998244353よりN≤2×10^5が小さいので、使うN−1とC(N,2)は0にならない。小例N=3ではC_3=−1,e_3=−1/3となり、外部同士のpairがないことに対応する。

指数的な操作列全探索も値ごとの確率DPも不要であり、目的の次数に合わせて二次モーメントだけを残すのが鍵である。

典型の発動条件

交換対称性による期待値圧縮

発動条件: ランダム過程の最終係数が index permutation に対して対称なとき。

全 pair の相関を一つの N 依存値へまとめる。

一次 moment recurrence

発動条件: 最初の操作で二要素をまとめると小さい同型問題になるとき。

固定された交差項と残り問題の期待値を足して漸化式を作る。

問題固有の要素

最終値分布を求めず、目的関数を展開して必要な二次 moment だけを対称性で分類する。

別の問題へ持ち帰る視点: ランダム縮約過程では最初の一手を固定し、残った object が一サイズ小さい同分布になるかを見る。

正当性

各初期値の係数は、減算併合ごとに符号が掛かるだけなので±1であり、x²の対角項はΣA_i²。添字交換で操作の分布が変わらないため、異なる全pairの相関は共通e_Nである。

初手の二係数は小問題の合成要素の符号dと−dになり、互いの積は−1、外部との二つの積は個々の操作列でも相殺する。外部N−2要素のpairだけが小問題の共通相関e_{N−1}を残すので、C_N=−1+C(N−2,2)e_{N−1}。N≥3ではpair数の比が(N−3)/(N−1)となる。基底C_1=0,C_2=−1からこの再帰は全相関和を計算し、全pairの共通値へ戻したe_Nを二次式へ代入すると求める期待値になる。

実装上の注意

  • N=1はA_1²、N=2はC_2=−1を基底にする。存在しないpairの逆元を取らない。
  • ΣA_iとΣA_i²は法上で集計してよい。最後の式はsumSq+e_N(sum²−sumSq)なのでpair和用の除算2を別に重ねない。
  • C_Nは全pairの相関和、e_Nは一pairの相関である。これらを取り違えるとN≥3で倍率が変わる。

復習の核

  • 最初の二要素に関する三種類の pair(互い・片方と外部・外部同士)の寄与を分けて C_N の式を再導出する。

計算量と制約

時間

N 要素。整数逆元を1..Nで前計算すれば recurrenceと集約は O(N)。各stepでべき逆元を計算する実装は O(Nlog p)、p=998244353。

空間

逆元表O(N)、入力逐次sumとsumSq集約ならそれ以外O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq A_i \leq 998244352; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Random Subtraction の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 確率・期待値DP

    補助タグ: 法上の四則演算・高速累乗・逆元 状態・配置の正規化

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

    学習の位置

    体系上の位置: 確率過程・期待値DP

    • 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。

    先に読む単元:

    この解説で扱わないこと:

    • 二人零和ゲームの勝敗・Grundy数。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題