factorial convolutionによる多項式Taylor shift
P(x+a) の全係数を二項展開し、階乗倍した係数列と a^i/i! の反転畳み込みへ変換して準線形時間で求める。
この典型を扱う単元: factorial convolutionによる多項式Taylor shift
検索別名: factorial convolution shift、polynomial Taylor shift、多項式Taylor shift、多項式平行移動
未知問からこの典型を見つける手掛かり
- 扱う対象
- factorial-scaled sequence
- polynomial coefficients
- shift parameter
- 使う手掛かり
- P\(x\+a\) の全係数
- binomial expansion becomes convolution
- 一つの平行移動を高速化
- 保つ不変量
- binomial coefficient factorization
- coefficient reversal
- degree bound
- 求めるもの
- shifted polynomial coefficients
- 準線形Taylor shift
- 適用しない条件
- 一般の f\(g\(x\)\) を計算する
- 多数の点での値だけを求める
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
- 畳み込み・相互相関: P(x+a)の係数式を階乗で正規化し、係数反転を施した二列の一回の畳み込みへ意味保存変換する。
学習成果と学習単位
二項係数を階乗で分離し、係数列の反転と一回の畳み込みから P(x+a) の全係数を準線形時間で復元できる。
factorial convolutionによる多項式Taylor shiftで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC323 G「Inversion of Tree」 公式問題主題: 行列式による数え上げ / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC323 G「Inversion of Tree」 公式問題主題: 行列式による数え上げ / 補助タグ