法上の動的積・剰余 0 因子の分離
取り得る因子のうち法 m で非零となるものがすべて可逆であることを確認し、因子の差し替えを「剰余 0 の因子数」と「非零因子の積」に分け、可逆な旧因子を逆元で外して新因子を掛ける。
この典型を扱う単元: 可逆な非零剰余と剰余 0 因子を含む法上の動的積
検索別名: dynamic modular product、zero-aware modular product、剰余 0 因子数と可逆な非零剰余因子の積、法上の動的積
未知問からこの典型を見つける手掛かり
- 扱う対象
- mod
- 剰余
- 因子
- 更新
- 積
- 使う手掛かり
- 0.*逆元
- 0.*除けない
- 一因子.*更新
- 因子.*差し替
- 積.*更新
- 保つ不変量
- 0.*因子.*個数
- zero count
- 非零.*可逆
- 非零因子積
- 求めるもの
- 動的.*積
- 更新後.*積
- 法上.*積
- 適用しない条件
- すべての因子を毎回走査
- 加算だけ
- 積を更新しない
分類・前提・学習成果
分類と直接の前提
概念上の親: 法上の四則演算・高速累乗・逆元
関連する典型
学習成果と学習単位
法 m 上の積で一因子を差し替えるとき、取り得る因子のうち非零剰余がすべて可逆かを確認し、剰余 0 の因子数と可逆な非零剰余因子の積を分離して、可逆な旧因子を逆元で除き新因子を掛けて更新後の積を復元できる。
可逆な非零剰余と剰余 0 因子を含む法上の動的積で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC405 G「Range Shuffle Query」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約
- ABC411 E「E [max]」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換、法上の動的積・剰余 0 因子の分離 / 補助タグ: event・値順のオフライン走査、法上の四則演算・高速累乗・逆元
- ABC456 G「Count Holidays」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC405 G「Range Shuffle Query」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約
- ABC411 E「E [max]」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換、法上の動的積・剰余 0 因子の分離 / 補助タグ: event・値順のオフライン走査、法上の四則演算・高速累乗・逆元
- ABC456 G「Count Holidays」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ