法上の四則演算・高速累乗・逆元
剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算・確率を計算する。
この典型を扱う単元: 法上の四則演算・高速累乗・逆元
検索別名: modular arithmetic、modular exponentiation、modular inverse、モジュラ逆元、法上の四則演算
未知問からこの典型を見つける手掛かり
- 扱う対象
- mod
- 剰余
- 法
- 確率
- 逆元
- 使う手掛かり
- modを取る
- 二分累乗
- 法で割る
- 逆元を掛ける
- 保つ不変量
- 乗法単位元
- 合同類
- 正規化
- 逆元の存在
- 求めるもの
- 剰余での確率
- 巨大冪
- 法上の値
- 法上の除算
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 数論構造への変換
関連する典型
学習成果と学習単位
剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。
法上の四則演算・高速累乗・逆元で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC212 H「Nim Counting」 公式問題主題: 分離可能線形変換・Walsh–Hadamard変換 / 補助タグ
技能・出典
主タグ: 分離可能線形変換・Walsh–Hadamard変換 / 補助タグ: game状態・Grundy DP、法上の四則演算・高速累乗・逆元
- ABC215 G「Colorful Candies 2」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC216 H「Random Robots」 公式問題主題: 行列式による数え上げ / 補助タグ
- ABC220 E「Distance on Large Perfect Binary Tree」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC221 E「LEQ」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、法上の四則演算・高速累乗・逆元
- ABC222 H「Beautiful Binary Tree」 公式問題主題: 母関数方程式・高度な係数抽出 / 補助タグ
- ABC226 E「Just one」 公式問題主題: 単一サイクル成分とgraph core / 補助タグ
- ABC226 F「Score of Permutations」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC226 H「Random Kth Max」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC228 E「Integer Sequence Fair」 公式問題主題: 剰余周期と指数法則を利用する / 主タグ
- ABC231 G「Balls in Boxes」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC234 F「Reordering」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC235 G「Gardens」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC238 Ex「Removing People」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
技能・出典
主題: 時間を逆向きにして未来依存を消す
主タグ: 逆向きのオフライン処理 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、区間合成・領域分割DP、法上の四則演算・高速累乗・逆元
- ABC239 Ex「Dice Product 2」 公式問題主題: 整数境界と同値区間を正確に分ける / 補助タグ
- ABC241 Ex「Card Deck Score」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC242 Ex「Random Painting」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC243 F「Lottery」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC245 Ex「Product Modulo 2」 公式問題主題: 一次合同・CRTで解の類を統合する / 補助タグ
- ABC246 F「typewriter」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC249 Ex「Dye Color」 公式問題主題: 期待値の頻度圧縮と加法的ポテンシャル / 補助タグ
- ABC253 Ex「We Love Forest」 公式問題主題: 行列式による数え上げ / 補助タグ
- ABC256 F「Cumulative Cumulative Cumulative Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC262 E「Red and Blue Graph」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC263 E「Sugoroku 3」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC268 G「Random Student ID」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC269 F「Numbered Checker」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC270 Ex「add 1」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC270 G「Sequence in mod P」 公式問題主題: Baby-Step Giant-Step・可逆作用の反復到達探索 / 補助タグ
技能・出典
主題: Baby-Step Giant-Step・可逆作用の反復到達探索
主タグ: Baby-Step Giant-Step・可逆作用の反復到達探索 / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC271 G「Access Counter」 公式問題主題: 固定線形遷移を巨大回数進める / 補助タグ
- ABC275 E「Sugoroku 4」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC276 F「Double Chance」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
- ABC277 G「Random Walk to Millionaire」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC280 E「Critical Hit」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC282 E「Choose Two and Eat One」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
- ABC284 Ex「Count Unlabeled Graphs」 公式問題主題: 群作用・軌道数え上げ / 補助タグ
- ABC284 G「Only Once」 公式問題主題: 関数グラフのcycle・tree分解 / 補助タグ
- ABC289 Ex「Trio」 公式問題主題: FPS基本演算と多項式の多点評価を行う / 補助タグ
技能・出典
主タグ: 畳み込み・相互相関、形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC295 E「Kth Number」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC297 Ex「Diff Adjacent」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC297 F「Minimum Bounding Box 2」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC298 E「Unfair Sugoroku」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC299 Ex「Dice Sum Infinity」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC300 E「Dice Product 3」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成 / 補助タグ
- ABC303 Ex「Constrained Tree Degree」 公式問題主題: Prüfer code・次数制約付きlabel木 / 補助タグ
技能・出典
主タグ: Prüfer code・次数制約付きlabel木 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、生成関数による組合せ構造の符号化、法上の四則演算・高速累乗・逆元
- ABC304 F「Shift Table」 公式問題主題: 約数格子のzeta・Möbius反転 / 補助タグ
- ABC310 F「Make 10 Again」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC310 G「Takahashi And Pass-The-Ball Game」 公式問題主題: doubling・binary lifting / 補助タグ
- ABC314 F「A Certain Game」 公式問題主題: DSU merge tree・Kruskal reconstruction tree / 補助タグ
- ABC321 G「Electric Circuit」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC323 E「Playlist」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC326 E「Revenge of "The Salary of AtCoder Inc."」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC327 G「Many Good Tuple Problems」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC330 G「Inversion Squared」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC331 G「Collect Them All」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
技能・出典
主タグ: 生成関数による組合せ構造の符号化、集合上の包除原理 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC332 F「Random Update Query」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC333 F「Bomb Game 2」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC334 E「Christmas Color Grid 1」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC334 G「Christmas Color Grid 2」 公式問題主題: lowlinkで橋・関節点を特定する / 補助タグ
- ABC335 G「Discrete Logarithm Problems」 公式問題主題: 巡回群を指数化して数える / 補助タグ
技能・出典
主題: 巡回群を指数化して数える
主タグ: 巡回群の指数化・位数別数え上げ、乗法的位数・最小周期 / 補助タグ: 約数格子のzeta・Möbius反転、法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC336 G「16 Integers」 公式問題主題: BEST定理によるEuler circuit数え上げ / 補助タグ
- ABC345 G「Sugoroku 5」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、再帰分割・分割統治、平方根・閾値による軽重分類
- ABC349 F「Subsequence LCM」 公式問題主題: subset zeta・Möbius変換 / 補助タグ
- ABC352 G「Socks 3」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC360 E「Random Swaps of Balls」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC377 E「Permute K times 2」 公式問題主題: 関数グラフのcycle・tree分解 / 補助タグ
- ABC380 G「Another Shuffle Window」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元、尺取り法・sliding window
- ABC405 E「Fruit Lineup」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC409 G「Accumulation of Wealth」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
技能・出典
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC411 E「E [max]」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換、法上の動的積・剰余 0 因子の分離 / 補助タグ: event・値順のオフライン走査、法上の四則演算・高速累乗・逆元
- ABC411 G「Count Cycles」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC412 F「Socks 4」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC417 F「Random Gathering」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC422 G「Balls and Boxes」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC428 G「Necklace」 公式問題主題: 群作用・軌道数え上げ / 補助タグ
- ABC432 G「Sum of Binom(A, B)」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
- ABC439 F「Beautiful Kadomatsu」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元
- ABC439 G「Sugoroku 6」 公式問題主題: FPS合成・power projection / 補助タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC445 E「Many LCMs」 公式問題主題: 素因数分解と約数構造 / 補助タグ
- ABC448 E「Simple Division」 公式問題主題: monoid exponentiation・連結演算doubling / 補助タグ
技能・出典
主題: monoid exponentiation・連結演算doubling
主タグ: monoid exponentiation・連結演算doubling / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC450 G「Random Subtraction」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC455 F「Merge Slimes 2」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC462 G「Completely Wrong」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC463 F「Senshuraku」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC463 G「Random Walk Distance」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC464 F「Random Vault Heist」 公式問題主題: meet-in-the-middle・半分全列挙 / 補助タグ
技能・出典
主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元