生成関数による組合せ構造の符号化
和・積・sequence・set・cycleなどの組合せ構成を係数列の演算へ翻訳し、欲しい個数を係数として抽出する。
この典型を扱う単元: 組合せを生成関数へ符号化する
検索別名: generating function、母関数、生成関数
未知問からこの典型を見つける手掛かり
- 扱う対象
- OGF/EGF
- 係数列
- 組合せclass
- 使う手掛かり
- 独立な合成
- 連結成分へ分解
- 保つ不変量
- sizeに対する係数
- 全単射
- 求めるもの
- 係数抽出
- 数え上げ式
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
- 畳み込み・相互相関: 組合せの合成を生成関数の積へ符号化し、その係数を畳み込みで計算する流れで併用する。
学習成果と学習単位
組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。
組合せを生成関数へ符号化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC214 G「Three Permutations」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC225 H「Social Distance 2」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC231 G「Balls in Boxes」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC235 Ex「Painting Weighted Graph」 公式問題
- ABC241 Ex「Card Deck Score」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC247 Ex「Rearranging Problem」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC267 Ex「Odd Sum」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC269 Ex「Antichain」 公式問題主題: heavy path上の多項式木DP / 補助タグ
技能・出典
主タグ: heavy path上の多項式木DP / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化、再帰分割・分割統治、根付き木DP・部分木集約
- ABC272 Ex「Flipping Coins 2」 公式問題主題: 多項式の多点評価・補間 / 主タグ
技能・出典
主題: 多項式の多点評価・補間
主タグ: 生成関数による組合せ構造の符号化、多項式の多点評価・補間 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、再帰分割・分割統治
- ABC281 Ex「Alchemy」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC285 Ex「Avoid Square Number」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC289 Ex「Trio」 公式問題主題: FPS基本演算と多項式の多点評価を行う / 主タグ
技能・出典
主タグ: 畳み込み・相互相関、形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC297 Ex「Diff Adjacent」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC303 Ex「Constrained Tree Degree」 公式問題主題: Prüfer code・次数制約付きlabel木 / 補助タグ
技能・出典
主タグ: Prüfer code・次数制約付きlabel木 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、生成関数による組合せ構造の符号化、法上の四則演算・高速累乗・逆元
- ABC315 Ex「Typical Convolution Problem」 公式問題主題: Relaxed・online convolution / 補助タグ
技能・出典
主題: Relaxed・online convolution
主タグ: Relaxed・online convolution / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化
- ABC317 Ex「Walk」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC318 Ex「Count Strong Test Cases」 公式問題主題: label付き連結成分分解・exponential formula / 補助タグ
- ABC331 G「Collect Them All」 公式問題主題: 包除・Möbius反転で重複を補正する / 主タグ
技能・出典
主タグ: 生成関数による組合せ構造の符号化、集合上の包除原理 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC345 G「Sugoroku 5」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、再帰分割・分割統治、平方根・閾値による軽重分類
- ABC352 G「Socks 3」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC367 G「Sum of (XOR^K or 0)」 公式問題主題: 分離可能線形変換・Walsh–Hadamard変換 / 補助タグ
- ABC385 G「Counting Buildings」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC387 G「Prime Circuit」 公式問題主題: FPS合成・power projection / 主タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関
- ABC389 G「Odd Even Graph」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC390 G「Permutation Concatenation」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC392 G「Fine Triplets」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 主タグ
- ABC409 G「Accumulation of Wealth」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 主タグ
技能・出典
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC422 G「Balls and Boxes」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC432 G「Sum of Binom(A, B)」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 主タグ
- ABC436 G「Linear Inequation」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC439 G「Sugoroku 6」 公式問題主題: FPS合成・power projection / 主タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC449 G「Many Repunit Sum 2」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC462 G「Completely Wrong」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ