形式的べき級数の基本演算
定数項条件と次数打切りを確認し、Newton iterationでinverse・log・exp等を畳み込みへ還元する。
この典型を扱う単元: FPS基本演算と多項式の多点評価を行う
検索別名: FPS、Newton iteration、formal power series、形式的べき級数
未知問からこの典型を見つける手掛かり
- 扱う対象
- constant term
- formal series
- truncation degree
- 使う手掛かり
- inverse/log/exp
- 次数を倍増
- 保つ不変量
- Newton誤差次数
- mod x\^n
- 求めるもの
- FPS演算
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
- 畳み込み・相互相関: Newton iterationの各段で必要な積・逆数更新を高速多項式畳み込みで実装する。
学習成果と学習単位
定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。
FPS基本演算と多項式の多点評価を行うで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC260 Ex「Colorfulness」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC289 Ex「Trio」 公式問題主題: FPS基本演算と多項式の多点評価を行う / 主タグ
技能・出典
主タグ: 畳み込み・相互相関、形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC297 Ex「Diff Adjacent」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
技能・出典
主題: 組合せを生成関数へ符号化する
主タグ: 形式的べき級数の基本演算、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、集合上の包除原理、法上の四則演算・高速累乗・逆元
- ABC317 Ex「Walk」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ
- ABC318 Ex「Count Strong Test Cases」 公式問題主題: label付き連結成分分解・exponential formula / 主タグ
- ABC387 G「Prime Circuit」 公式問題主題: FPS合成・power projection / 主タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関
- ABC439 G「Sugoroku 6」 公式問題主題: FPS合成・power projection / 主タグ
技能・出典
主タグ: 形式的べき級数の基本演算、FPS合成・power projection、生成関数による組合せ構造の符号化 / 補助タグ: 畳み込み・相互相関、法上の四則演算・高速累乗・逆元、再帰分割・分割統治
- ABC449 G「Many Repunit Sum 2」 公式問題主題: 組合せを生成関数へ符号化する / 主タグ