可逆な非零剰余と剰余 0 因子を含む法上の動的積

概要

法上の動的積・剰余 0 因子の分離

取り得る因子のうち法 m で非零となるものがすべて可逆であることを確認し、因子の差し替えを「剰余 0 の因子数」と「非零因子の積」に分け、可逆な旧因子を逆元で外して新因子を掛ける。

考え方

積を一つの剰余だけで保持すると、因子を掛けて0になった時点で、それまでの非零因子の情報を失う。後で剰余0の因子を削除しても、0を逆元で割って元へ戻すことはできない。そこで、法を整数 m≥2m\geq2 とし、次の二つを保持する。

  • zz: 剰余が0となる因子の個数。
  • PP: 剰余が非零の因子だけを掛けた積の剰余。

取り得る非零剰余がすべて可逆であることを前提とする。素数法ならこの条件を満たす。保持した状態から、全体の積は z>0z>0 なら0、z=0z=0 なら PP と復元できる。

法7で因子2、7、14を順に挿入し、7、14を順に削除してみよう。7も14も整数としては0でないが、剰余は0なので zz に数える。空積は1とし、最初は z=0,P=1z=0,P=1 である。表の因子は整数値を、「積」は全因子の積の剰余を示す。

操作因子zzPP積
開始なし011
2を挿入2022
7を挿入2, 7120
14を挿入2, 7, 14220
7を削除2, 14120
14を削除2022

積が0の間も P=2P=2 を保持しているため、最後の剰余0因子が消えたときに2へ復帰できる。零の有無だけでなく個数を持つのは、7を一つ削除しても14が残っていることを区別するためである。

更新する因子の整数値を xx とし、まず r=((x mod m)+m) mod mr=((x\bmod m)+m)\bmod m で剰余を正規化する。例えば法7では x=−7x=-7 は剰余0として、x=−1x=-1 は剰余6として扱う。

  • 挿入: r=0r=0 なら zz を1増やす。非零なら P←Pr mod mP\leftarrow Pr\bmod m とする。
  • 削除: 現在存在する因子を一つ取り除く。r=0r=0 なら zz を1減らす。非零なら P←Pr−1 mod mP\leftarrow Pr^{-1}\bmod m とする。
  • 差し替え: 旧値を削除してから新値を挿入し、両方が終わった状態から全体の積を取り出す。

各操作は zz と PP の定義を保つ。非零因子の削除は、その因子と逆元の積が1になるため、残りの非零因子だけの積を返す。これは z>0z>0 の間も省略してはいけない。例えば表の因子が2、7、14の時点で2を3へ差し替えるなら、2−1≡4(mod7)2^{-1}\equiv4\pmod7 を使って P←2⋅4⋅3 mod 7=3P\leftarrow2\cdot4\cdot3\bmod7=3 と更新する。全体の積はまだ0だが、その後7と14を削除したときには3へ復帰する。すべての因子を削除すれば、空積を表す z=0,P=1z=0,P=1 に戻る。

合成数法でも、非零因子がすべて単元(逆元を持つ剰余)なら使える。例えば法6の5は 5⋅5≡1(mod6)5\cdot5\equiv1\pmod6 なので取り除ける。一方、非零の2は逆元を持たない。因子2と3の積は法6で0になるが、上の定義では z=0,P=0z=0,P=0 であり、剰余0因子だけを数えても、この逆元による削除は実現できない。このような非可逆な非零因子を扱う場合は、素因数指数の分離など別の表現が必要になる。

ABC411 Eでは、各サイコロの「閾値以下の面数」の積を保つ。面数が0のサイコロが残る間も、正の面数の積を更新しておけば、すべてのサイコロで面数が正になった時点の積が得られる。

成立条件と計算量

初期の因子数を nn、以後の更新回数を QQ とする。初期状態は各因子を一度ずつ挿入して O(n)O(n) 回の算術演算で作れる。逆元をその都度求める場合、非零因子の削除・差し替えは一回 O(log⁡m)O(\log m) 回、全体は O(n+Qlog⁡m)O(n+Q\log m) 回の算術演算となる。素数法では二分累乗、合成数法の単元では拡張ユークリッドの互除法で逆元を作る。

必要な逆元が既知なら一更新は O(1)O(1) 回であり、全体はその前計算に O(n+Q)O(n+Q) 回を加えた計算量になる。例えばABC411 Eの非零面数は1から6だけなので、逆元を先に求められる。積の保守に必要な追加状態は z,Pz,P の O(1)O(1) 空間である。位置を指定して差し替えるなら旧値を保持する O(n)O(n) 空間も必要になる。逆元の表を作る場合は、その領域も別に数える。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。逆元で除ける因子を確認し、0の個数と非零因子の積を分けて更新する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 法上の演算と積の保守。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dynamic-modular-product

習得する技能

  • 法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 法上の四則演算・高速累乗・逆元。

このUnitを直接前提とする単元: なし。

通常の法上演算と逆元の存在条件を前提に、取り得る因子のうち法 mm で非零となるものがすべて可逆(典型的には素数法)かを確認する。剰余0の因子の個数と可逆な非零剰余因子の積へ状態を分け、必要な逆元が既知なら因子差し替えを定数時間で処理する。

このUnitでは扱わないもの

  • 因子が変化しない一回限りの積、和やmin/maxの更新、任意区間積を求めるSegment Tree、および合成数法で非零の非可逆因子も差し替える一般の場合。

根拠