寄与の数え上げと順序交換
数える対象を要素・組・値・区間ごとに一意に固定し、その対象を含む選択の個数や指示変数の期待値を先に集計する。
この典型を扱う単元: 局所寄与へ分解して集計順を交換する
検索別名: contribution technique、主客転倒
未知問からこの典型を見つける手掛かり
- 扱う対象
- 値
- 区間
- 合計
- 対
- 指示変数
- 組
- 要素
- 使う手掛かり
- 二重和
- 寄与
- 対象を固定
- 数え上げ順序
- 期待値の線形性
- 保つ不変量
- 一意
- 何回数え
- 係数
- 含まれる回数
- 重複
- 求めるもの
- 場合の数
- 期待値
- 総和
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。
局所寄与へ分解して集計順を交換するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC215 G「Colorful Candies 2」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC216 F「Max Sum Counting」 公式問題主題: 資源・容量DP / 補助タグ
- ABC219 H「Candles」 公式問題主題: 区間拡張DP / 補助タグ
- ABC220 E「Distance on Large Perfect Binary Tree」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC221 E「LEQ」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、法上の四則演算・高速累乗・逆元
- ABC221 F「Diameter set」 公式問題主題: 基準点からの木距離・剰余類・直径・中心 / 補助タグ
- ABC222 E「Red and Blue Tree」 公式問題主題: 資源・容量DP / 補助タグ
- ABC224 F「Problem where +s Separate Digits」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC231 G「Balls in Boxes」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC233 E「Σ[k=0..10^100]floor(X/10^k)」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC238 Ex「Removing People」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
技能・出典
主題: 時間を逆向きにして未来依存を消す
主タグ: 逆向きのオフライン処理 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、区間合成・領域分割DP、法上の四則演算・高速累乗・逆元
- ABC247 E「Max Min」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC255 E「Lucky Numbers」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC258 G「Triangle」 公式問題主題: bitsetで集合演算をword並列化する / 補助タグ
- ABC261 F「Sorting Color Balls」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC262 Ex「Max Limited Sequence」 公式問題主題: prefix分割DP / 補助タグ
- ABC268 G「Random Student ID」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC269 F「Numbered Checker」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC277 G「Random Walk to Millionaire」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC280 E「Critical Hit」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC280 G「Do Use Hexagon Grid 2」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC283 Ex「Popcount Sum」 公式問題主題: 格子点転置によるfloor_sum / 補助タグ
- ABC290 E「Make it Palindrome」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC295 E「Kth Number」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC295 F「substr = S」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC297 F「Minimum Bounding Box 2」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC306 F「Merge Sets」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC308 E「MEX」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC313 F「Flip Machines」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC314 F「A Certain Game」 公式問題主題: DSU merge tree・Kruskal reconstruction tree / 補助タグ
- ABC318 E「Sandwiches」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC321 G「Electric Circuit」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC324 E「Joint Two Strings」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC326 E「Revenge of "The Salary of AtCoder Inc."」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC330 G「Inversion Squared」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC334 E「Christmas Color Grid 1」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC347 E「Set Add Query」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC351 E「Jump Distance Sum」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC352 G「Socks 3」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC353 E「Yet Another Sigma Problem」 公式問題主題: Trieで共有接頭辞を索引化する / 補助タグ
- ABC359 G「Sum of Tree Distance」 公式問題主題: 木の均衡分離点から重心分解へ進む / 補助タグ
- ABC362 F「Perfect Matching on a Tree」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC365 E「Xor Sigma Problem」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC371 E「I Hate Sigma Problems」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC378 E「Mod Sigma Problem」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC379 E「Sum of All Substrings」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC380 G「Another Shuffle Window」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元、尺取り法・sliding window
- ABC386 G「Many MST」 公式問題主題: label付き連結成分分解・exponential formula / 主タグ
技能・出典
主題: label付き連結成分分解・exponential formula
主タグ: 寄与の数え上げと順序交換、label付き連結成分分解・exponential formula / 補助タグ: 組合せ係数・数え上げ
- ABC390 F「Double Sum 3」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC390 G「Permutation Concatenation」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC396 F「Rotated Inversions」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC401 F「Add One Edge 3」 公式問題主題: 基準点からの木距離・剰余類・直径・中心 / 補助タグ
- ABC407 F「Sums of Sliding Window Maximum」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理、累積和・差分配列
- ABC411 E「E [max]」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換、法上の動的積・剰余 0 因子の分離 / 補助タグ: event・値順のオフライン走査、法上の四則演算・高速累乗・逆元
- ABC417 F「Random Gathering」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC418 E「Trapezium」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC422 F「Eat and Ride」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC423 E「Sum of Subarrays」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC433 F「1122 Subsequence 2」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC436 F「Starry Landscape Photo」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC438 F「Sum of Mex」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
- ABC439 F「Beautiful Kadomatsu」 公式問題主題: 局所寄与へ分解して集計順を交換する / 主タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元
- ABC455 F「Merge Slimes 2」 公式問題主題: 区間更新を要約へ作用させる / 補助タグ
- ABC464 F「Random Vault Heist」 公式問題主題: meet-in-the-middle・半分全列挙 / 補助タグ
技能・出典
主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元