ABC 293 E — Geometric Progression

考察

等比和a_n=Σ_(i=0)^(n-1)A^iはa_(n+1)=A a_n+1という一次アフィン漸化式を満たす。状態(a_n,1)へ行列[[A,1],[0,1]]を掛けると、除算なしで和と冪を同時に合成できる。

採用する候補: 2×2行列の高速累乗

アフィン更新を線形化すれば合成を法M上で安全に繰り返し二乗できる。

棄却する候補: (A^X-1)/(A-1)を法上で割る

Mは素数とは限らずA-1の逆元が存在しない場合がある。

遷移行列を法MでX乗し、初期ベクトル(0,1)へ作用させた第一成分を出力する。

典型の発動条件

アフィン変換の行列化

発動条件: 定数項付き漸化式を巨大回反復する。

定数1を状態へ加え2×2行列として累乗する。

問題固有の要素

閉形式の割り算が危険な合成数modでも、漸化式の合成なら加減乗だけで完結する。

別の問題へ持ち帰る視点: 法上の逆元が保証されない等比和は行列・doublingで求める。

正当性

f(n+1)=Af(n)+1、f(0)=0 は幾何和に一致する。定数1を添えたvectorへの行列作用はこのaffine更新と同じで、行列積は操作合成に一致する。二分累乗でX回合成した第一成分が答え。法M上でも除算を用いないので合成数とA=1を扱える。

実装上の注意

  • 全乗算を都度mod Mし、X=1、M=1、A=1でも同じ式で処理する。

復習の核

  • 直接和を作れる小Xと比較し、A=1、Mが合成数、A-1とMが非互いに素な例を確認する。

計算量と制約

時間

指数Xのbit数分の2×2行列積で O(log(X+1))。

空間

2×2行列を数個保持して O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq A, M \leq 10^9; 1 \leq X \leq 10^{12}; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Geometric Progression の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 固定線形遷移を巨大回数進める

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

      主タグ: 線形遷移・行列累乗

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

      学習の位置

      体系上の位置: 固定線形遷移を巨大回数進める

      • 固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。

      先に読む単元:

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

      • 一般のDP遷移の区間集約・単調最適化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題