畳み込み・相互相関
係数積和または反転列とのcorrelationを多項式積へ写し、必要な次数範囲をNTT/FFTで計算する。
この典型を扱う単元: NTT・FFTで畳み込みと相互相関を求める
検索別名: FFT、NTT、convolution、畳み込み
未知問からこの典型を見つける手掛かり
- 扱う対象
- 係数列
- 多項式
- 積和
- 使う手掛かり
- i\+j=k
- shiftごとの一致数
- 保つ不変量
- 係数積
- 次数範囲
- 求めるもの
- 係数列
- 相互相関
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
- 生成関数による組合せ構造の符号化: 組合せの合成を生成関数の積へ符号化し、その係数を畳み込みで計算する流れで併用する。
- subset convolution: 分解ごとの積を足す二項演算としては共通するが、通常の添字加算 i+j=k とdisjoint subset分割は異なる合成則であり、互いを特殊化とはみなさない。
学習成果と学習単位
係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。
NTT・FFTで畳み込みと相互相関を求めるで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC225 H「Social Distance 2」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC235 Ex「Painting Weighted Graph」 公式問題主題: DSU merge tree・Kruskal reconstruction tree / 補助タグ
- ABC247 Ex「Rearranging Problem」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC265 Ex「No-capture Lance Game」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 主タグ
技能・出典
主タグ: 畳み込み・相互相関 / 補助タグ: 独立な数ゲームの和、game状態・Grundy DP、分離可能線形変換・Walsh–Hadamard変換
- ABC267 Ex「Odd Sum」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC269 Ex「Antichain」 公式問題主題: heavy path上の多項式木DP / 補助タグ
技能・出典
主タグ: heavy path上の多項式木DP / 補助タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化、再帰分割・分割統治、根付き木DP・部分木集約
- ABC272 Ex「Flipping Coins 2」 公式問題主題: 多項式の多点評価・補間 / 補助タグ
技能・出典
主題: 多項式の多点評価・補間
主タグ: 生成関数による組合せ構造の符号化、多項式の多点評価・補間 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、再帰分割・分割統治
- ABC278 Ex「make 1」 公式問題主題: 組合せ係数と対称性で数える / 補助タグ
- ABC281 Ex「Alchemy」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
- ABC289 Ex「Trio」 公式問題主題: FPS基本演算と多項式の多点評価を行う / 主タグ
技能・出典
主タグ: 畳み込み・相互相関、形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC291 G「OR Sum」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 主タグ
- ABC297 Ex「Diff Adjacent」 公式問題主題: 組合せを生成関数へ符号化する / 補助タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC300 Ex「Fibonacci: Revisited」 公式問題主題: Bostan–Mori・有理生成関数の係数抽出 / 補助タグ
- ABC303 Ex「Constrained Tree Degree」 公式問題主題: Prüfer code・次数制約付きlabel木 / 補助タグ
技能・出典
主タグ: Prüfer code・次数制約付きlabel木 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、生成関数による組合せ構造の符号化、法上の四則演算・高速累乗・逆元
- ABC307 Ex「Marquee」 公式問題主題: NTT・FFTで畳み込みと相互相関を求める / 主タグ
- ABC309 Ex「Simple Path Counting Problem」 公式問題主題: 鏡像法・reflection principle / 補助タグ
- 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」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 畳み込み・相互相関、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、寄与の数え上げと順序交換、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC381 G「Fibonacci Product」 公式問題主題: 拡大有限体の表現と四則演算を構成する / 補助タグ
- ABC385 G「Counting Buildings」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC387 G「Prime Circuit」 公式問題主題: FPS合成・power projection / 補助タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関
- 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、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC462 G「Completely Wrong」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ