概要

何回勉強しても忘れてしまう「形式的冪級数」についてのメモ．

FPS が使えると何が嬉しいのか

いわゆる「数え上げ」ができるようになる．DP で解けるやつも FPS で解けたりする．

FPS 学習ステップ

高校卒業程度の数学能力を有している前提で，以下 2 ステップが必要．

  1. 「数え上げ → 多項式・形式的冪級数への言い換え」ができるようになる
  2. 「多項式・形式的冪級数 → 実際の係数の値を求める」ができるようになる

ステップ1. 「数え上げ → 多項式・形式的冪級数への言い換え」

まずは次の記事を読む．とてもわかりやすい．

また，分割数や累積和からの言い換えは，以下でも解説されている．読んでみると理解を深められるはず．

結局，どうやって言い換えるのか

$f=\sum_{(状態)}\ (場合の数)x^{(状態を表す式)}$ の形で式を書く．この形の多項式同士を掛け合わせると，指数部（状態を表す式）を見ると加算，係数（場合の数）を見ると乗算が行われることになる．状態 $n$ に対応する場合の数が欲しいときは， $f$ の $x^n$ の係数を求めればよい．$f$ の $x^n$ の係数を，$[x^n]f$ と書く．

式変形が必要な場合

形式的冪級数で表せたとしても，そのままでは計算量的に扱えないこともある．そのようなときは，式変形を行って，頑張って扱える形にする．

また，式変形を行うことで見通しがよくなる．

式変形では，普通の文字式と同じく，等比数列の和の公式が使えるほか，類似するいくつかの典型的変形パターンが使える．

ステップ2. 多項式・形式的冪級数 → 実際の係数の値を求める

FPS ライブラリを借りるのが手っ取り早い．

以上