形式的べき級数解説

多項式・形式的べき級数を利用した問題の考察について、まとめていきます。

公開日
2020/01/04 (1)数え上げとの対応付け
2020/01/13 (2)式変形による解法の導出
2020/02/12 (3)線形漸化式と形式的べき級数
2022/04/26 高速に計算できるものたち (2024/04/04更新)
2022/08/31 (補足)定義や式変形の正当性の確認
2024/04/22 FPS 合成・逆関数の解説(1)逆関数と Power Projection
2024/04/24 FPS 合成・逆関数の解説(2)転置原理による合成アルゴリズムの導出

関連リンク

英語記事

スポンサーリンク
形式的べき級数解説

FPS Composition and Compositional Inverse (Part 2)

(Part 1) Compositional Inverse and Power Projection(Part 2) Composition Algorithm via Transposition Principle (Here) ...
形式的べき級数解説

FPS Composition and Compositional Inverse (Part 1)

(Part 1) Compositional Inverse and Power Projection (Here)(Part 2) Composition Algorithm via Transposition Principle ...
形式的べき級数解説

FPS 合成・逆関数の解説(2)転置原理による合成アルゴリズムの導出

概要 続きです. 前回 → FPS 合成・逆関数の解説(1)逆関数と Power Projection $f(x), g(x)$ を FPS とするとき,次のどちらかが成り立つ状況で合成 $f(g(x)) = \sum_...
形式的べき級数解説

FPS 合成・逆関数の解説(1)逆関数と Power Projection

概要 noshi91 さんにより,形式的べき級数の合成・逆関数を $\Theta(n\log^2 n)$ 時間で計算する方法が発表されました. これは基礎的な問題に対して簡潔なアルゴリズムで既知の計算量を改善するもので,国内・...
形式的べき級数解説

[多項式・形式的べき級数] (補足)定義や式変形の正当性の確認

この記事は、形式的べき級数の厳密な定義や、その正当性に疑問を感じた場合に見ることを想定しています。次の記事との関係については、どちらが先でも構いません。より手短に面白い所を勉強したり、問題解決に役立てたい場合には、先に(1)(2)(3)な...
形式的べき級数解説

[多項式・形式的べき級数] 高速に計算できるものたち

前提知識 (1)数え上げとの対応付け (2)式変形による解法の導出 (3)線形漸化式と形式的べき級数 上の 3 つの記事では,ほとんど他サイト等を参照せずに私の記事だけで解説を完結させるようにしていましたが,本...
形式的べき級数解説

[多項式・形式的べき級数](3)線形漸化式と形式的べき級数

シリーズ一覧 → ■ 関連解説:・ G – フィボナッチ数の総和(square869120Contest)・ E – Placing Squares(AGC 013) 有理式の構造 本記事では、有理式で表される形...
形式的べき級数解説

[多項式・形式的べき級数](2)式変形による解法の導出

概要 第1回:数え上げとの対応付け → ■ 前回は、いろいろな数え上げの問題が、多項式(形式的べき級数)の問題に変換されることを確認しました。しかしこれだけでは、通常の dp の考え方をそのまま翻訳しただけです。まぁデータの持...
形式的べき級数解説

[多項式・形式的べき級数](1)数え上げとの対応付け

(2)式変形による解法の導出(3)線形漸化式と形式的べき級数 概要 ある種の数え上げの計算は、多項式・形式的べき級数に対する計算と結び付けることができます。数え上げの問題を、多項式・形式的べき級数に対する計算と読み替えて、代数...
問題解説

形式的べき級数による数え上げ(JSC2019予選 [F])

概要 AtCoder 第一回 日本最強プログラマー学生選手権 -予選- → ■問題F - Candy Retribution → ■自分の提出 → ■ 私はこの問題は、コンテスト中には解ききれなかった(解き方は分かったものの、残り時...
スポンサーリンク
タイトルとURLをコピーしました