組合せ係数・数え上げ
選択順・順列・分配を二項係数や階乗と対称性で式化する。
この典型を扱う単元: 組合せ係数と対称性で数える
検索別名: binomial coefficients、二項係数、重複組合せ
未知問からこの典型を見つける手掛かり
- 扱う対象
- 並べ方
- 個数
- 場合の数
- 選び方
- 使う手掛かり
- 何通り
- 分配
- 選ぶ
- 順列
- 保つ不変量
- ncr
- 対称性
- 階乗
- 求めるもの
- 場合の数
- 確率
- 総数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
学習成果と学習単位
素数pのもとでn,kをp進展開し、Lucasの定理 C(n,k)=∏C(n_i,k_i) mod pで、n≥pでも階乗の零除算を避けて計算できる。
組合せ係数と対称性で数えるで学ぶ選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。
組合せ係数と対称性で数えるで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC234 F「Reordering」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC358 E「Alphabet Tiles」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC214 G「Three Permutations」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC215 G「Colorful Candies 2」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC216 H「Random Robots」 公式問題主題: 行列式による数え上げ / 補助タグ
- ABC217 F「Make Pair」 公式問題主題: 区間合成・領域分割DP / 補助タグ
- ABC225 H「Social Distance 2」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC226 F「Score of Permutations」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC234 F「Reordering」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC235 G「Gardens」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC238 Ex「Removing People」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
技能・出典
主題: 時間を逆向きにして未来依存を消す
主タグ: 逆向きのオフライン処理 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、区間合成・領域分割DP、法上の四則演算・高速累乗・逆元
- ABC240 G「Teleporting Takahashi」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC242 Ex「Random Painting」 公式問題主題: 確率過程・期待値DP / 補助タグ
- ABC242 F「Black and White Rooks」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC243 F「Lottery」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC249 Ex「Dye Color」 公式問題主題: 期待値の頻度圧縮と加法的ポテンシャル / 補助タグ
- ABC251 Ex「Fill Triangle」 公式問題主題: 標数pのFrobenius恒等式による反復高速化 / 補助タグ
技能・出典
主タグ: 標数pのFrobenius恒等式による反復高速化 / 補助タグ: 組合せ係数・数え上げ、ordered interval partition・ODT
- ABC256 F「Cumulative Cumulative Cumulative Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC256 G「Black and White Stones」 公式問題主題: 固定線形遷移を巨大回数進める / 補助タグ
- ABC259 Ex「Yet Another Path Counting」 公式問題主題: 平方根・閾値による軽重分類 / 補助タグ
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC262 E「Red and Blue Graph」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC266 G「Yet Another RGB Sequence」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC267 G「Increasing K Times」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC272 Ex「Flipping Coins 2」 公式問題主題: 多項式の多点評価・補間 / 補助タグ
技能・出典
主題: 多項式の多点評価・補間
主タグ: 生成関数による組合せ構造の符号化、多項式の多点評価・補間 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、再帰分割・分割統治
- ABC273 G「Row Column Sums 2」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC276 G「Count Sequences」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC278 Ex「make 1」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC279 Ex「Sum of Prod of Min」 公式問題主題: 母関数方程式・高度な係数抽出 / 補助タグ
- ABC281 G「Farthest City」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC284 Ex「Count Unlabeled Graphs」 公式問題主題: 群作用・軌道数え上げ / 補助タグ
- ABC284 G「Only Once」 公式問題主題: 関数グラフのcycle・tree分解 / 補助タグ
- ABC285 Ex「Avoid Square Number」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC288 Ex「A Nameless Counting Problem」 公式問題主題: 上限制約付き桁DP / 補助タグ
- ABC289 Ex「Trio」 公式問題主題: FPS基本演算と多項式の多点評価を行う / 補助タグ
技能・出典
主タグ: 畳み込み・相互相関、形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC290 F「Maximum Diameter」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC295 E「Kth Number」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC297 F「Minimum Bounding Box 2」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC303 Ex「Constrained Tree Degree」 公式問題主題: Prüfer code・次数制約付きlabel木 / 補助タグ
技能・出典
主タグ: Prüfer code・次数制約付きlabel木 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、生成関数による組合せ構造の符号化、法上の四則演算・高速累乗・逆元
- ABC309 G「Ban Permutation」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
技能・出典
主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、frontier/profile DP・境界状態圧縮、部分集合・bitmask状態DP
- ABC313 Ex「Group Photo」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC321 G「Electric Circuit」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC327 G「Many Good Tuple Problems」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC336 G「16 Integers」 公式問題主題: BEST定理によるEuler circuit数え上げ / 補助タグ
- ABC345 G「Sugoroku 5」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、再帰分割・分割統治、平方根・閾値による軽重分類
- ABC352 G「Socks 3」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC357 G「Stair-like Grid」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC358 E「Alphabet Tiles」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC386 G「Many MST」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
技能・出典
主題: label付き連結成分分解・exponential formula
主タグ: 寄与の数え上げと順序交換、label付き連結成分分解・exponential formula / 補助タグ: 組合せ係数・数え上げ
- ABC389 G「Odd Even Graph」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC390 G「Permutation Concatenation」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC392 G「Fine Triplets」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
- ABC399 F「Range Power Sum」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC405 E「Fruit Lineup」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC405 G「Range Shuffle Query」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約
- ABC409 G「Accumulation of Wealth」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
技能・出典
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC422 G「Balls and Boxes」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC425 E「Count Sequences 2」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC431 F「Almost Sorted 2」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC432 G「Sum of Binom(A, B)」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 補助タグ
- ABC433 F「1122 Subsequence 2」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC453 E「Team Division」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC456 G「Count Holidays」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC458 E「Count 123」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC459 E「Select from Subtrees」 公式問題主題: 根付き木DP・部分木集約 / 補助タグ
- ABC463 F「Senshuraku」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC463 G「Random Walk Distance」 公式問題主題: 組合せ係数と対称性で数える / 主タグ
- ABC464 F「Random Vault Heist」 公式問題主題: meet-in-the-middle・半分全列挙 / 補助タグ
技能・出典
主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元