可逆な非零剰余と剰余 0 因子を含む法上の動的積
概要
法上の動的積・剰余 0 因子の分離
取り得る因子のうち法 m で非零となるものがすべて可逆であることを確認し、因子の差し替えを「剰余 0 の因子数」と「非零因子の積」に分け、可逆な旧因子を逆元で外して新因子を掛ける。
考え方
積を一つの剰余だけで保持すると、因子を掛けて0になった時点で、それまでの非零因子の情報を失う。後で剰余0の因子を削除しても、0を逆元で割って元へ戻すことはできない。そこで、法を整数 とし、次の二つを保持する。
- : 剰余が0となる因子の個数。
- : 剰余が非零の因子だけを掛けた積の剰余。
取り得る非零剰余がすべて可逆であることを前提とする。素数法ならこの条件を満たす。保持した状態から、全体の積は なら0、 なら と復元できる。
法7で因子2、7、14を順に挿入し、7、14を順に削除してみよう。7も14も整数としては0でないが、剰余は0なので に数える。空積は1とし、最初は である。表の因子は整数値を、「積」は全因子の積の剰余を示す。
| 操作 | 因子 | 積 | ||
|---|---|---|---|---|
| 開始 | なし | 0 | 1 | 1 |
| 2を挿入 | 2 | 0 | 2 | 2 |
| 7を挿入 | 2, 7 | 1 | 2 | 0 |
| 14を挿入 | 2, 7, 14 | 2 | 2 | 0 |
| 7を削除 | 2, 14 | 1 | 2 | 0 |
| 14を削除 | 2 | 0 | 2 | 2 |
積が0の間も を保持しているため、最後の剰余0因子が消えたときに2へ復帰できる。零の有無だけでなく個数を持つのは、7を一つ削除しても14が残っていることを区別するためである。
更新する因子の整数値を とし、まず で剰余を正規化する。例えば法7では は剰余0として、 は剰余6として扱う。
- 挿入: なら を1増やす。非零なら とする。
- 削除: 現在存在する因子を一つ取り除く。 なら を1減らす。非零なら とする。
- 差し替え: 旧値を削除してから新値を挿入し、両方が終わった状態から全体の積を取り出す。
各操作は と の定義を保つ。非零因子の削除は、その因子と逆元の積が1になるため、残りの非零因子だけの積を返す。これは の間も省略してはいけない。例えば表の因子が2、7、14の時点で2を3へ差し替えるなら、 を使って と更新する。全体の積はまだ0だが、その後7と14を削除したときには3へ復帰する。すべての因子を削除すれば、空積を表す に戻る。
合成数法でも、非零因子がすべて単元(逆元を持つ剰余)なら使える。例えば法6の5は なので取り除ける。一方、非零の2は逆元を持たない。因子2と3の積は法6で0になるが、上の定義では であり、剰余0因子だけを数えても、この逆元による削除は実現できない。このような非可逆な非零因子を扱う場合は、素因数指数の分離など別の表現が必要になる。
ABC411 Eでは、各サイコロの「閾値以下の面数」の積を保つ。面数が0のサイコロが残る間も、正の面数の積を更新しておけば、すべてのサイコロで面数が正になった時点の積が得られる。
成立条件と計算量
初期の因子数を 、以後の更新回数を とする。初期状態は各因子を一度ずつ挿入して 回の算術演算で作れる。逆元をその都度求める場合、非零因子の削除・差し替えは一回 回、全体は 回の算術演算となる。素数法では二分累乗、合成数法の単元では拡張ユークリッドの互除法で逆元を作る。
必要な逆元が既知なら一更新は 回であり、全体はその前計算に 回を加えた計算量になる。例えばABC411 Eの非零面数は1から6だけなので、逆元を先に求められる。積の保守に必要な追加状態は の 空間である。位置を指定して差し替えるなら旧値を保持する 空間も必要になる。逆元の表を作る場合は、その領域も別に数える。
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC405 G「Range Shuffle Query」 公式問題
技能・出典
主題: Moの順序で区間問い合わせの差分を更新する(区間問い合わせの順序と追加・削除操作を設計し、端点移動の総量を評価できる。)。既習技能: 値軸のbucket分割と区間集約(値軸をblockへ分け、点更新で要約を差分修正し、完全blockと端数からprefixの和・積を取得できる。更新回数とquery回数に応じてblock幅を選べる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 可逆な非零剰余と剰余 0 因子を含む法上の動的積(法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。)。主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約
- ABC411 E「E [max]」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。追加で学ぶ技能: 可逆な非零剰余と剰余 0 因子を含む法上の動的積(法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 寄与の数え上げと順序交換、法上の動的積・剰余 0 因子の分離 / 補助タグ: event・値順のオフライン走査、法上の四則演算・高速累乗・逆元
- ABC456 G「Count Holidays」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 可逆な非零剰余と剰余 0 因子を含む法上の動的積(法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離
前提・学習成果・出典
習得対象の目安: 水色(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を直接前提とする単元: なし。
通常の法上演算と逆元の存在条件を前提に、取り得る因子のうち法 で非零となるものがすべて可逆(典型的には素数法)かを確認する。剰余0の因子の個数と可逆な非零剰余因子の積へ状態を分け、必要な逆元が既知なら因子差し替えを定数時間で処理する。
このUnitでは扱わないもの
- 因子が変化しない一回限りの積、和やmin/maxの更新、任意区間積を求めるSegment Tree、および合成数法で非零の非可逆因子も差し替える一般の場合。