多項式

数列の問題とか、組み合わせ問題を多項式の係数に置いて解くテクがある
はまやんはまやん自信作の解説 testestestさんのまとまった資料
母関数・形式的べき級数
- maspyさん資料1 maspyさん資料2 beetさん資料 latteさん資料
- 数列とかDPを母関数にして解く
- 計算過程で形式的べき級数を導入すると、計算できるようになったりする
- DPの遷移計算が多項式計算になれば、逆元が使えて遷移を「戻せる」 → 戻すDP
- 母関数は実際には関数じゃない、等比数列の総和っぽい計算してるけど違う結城先生ツイ1 結城先生ツイ2
- なんとなく、包除原理で頑張るか、形式的べき級数で殴るかの2つの解法がありそう
母関数・形式的べき級数の問題の流れ
- 1. 数列とかDPを母関数にする
- 1. うまいこといじると、多項式計算できる形になる
- 1. それを頑張って計算すると、求めたい数列とかDPになってる
多項式の計算
- 母関数とか形式的べき級数とかでコネコネすると多項式の計算に帰着できる
- その後の問題として多項式の計算をどう効率良くやるかという点が問題として残る
- rngさんの形式的べき級数での効率良く計算できるやつまとめ
- yosupoさんのverifyもすごく便利
- DPで計算したほうが早い系
  - *(1-xⁿ), /(1-xⁿ)
- (1+x+x²+...+xⁿ) = (1-xⁿ⁺¹)(1+x+x²+...) = (1-xⁿ⁺¹)/(1-x)
  - (1-xⁿ⁺¹)はFFTでやるよりDPの方で計算したほうが早い
  - /(1-x)は累積和と同じ計算になるので、累積和したほうが早い
  - どちらもO(N)でできるので、実はこの計算はO(N)でできる
  - → EDPC M Candies, ARC028 注文の多い高橋商店
- 多項式の累乗はFFTをして、各要素を累乗して、逆FFTをすれば実現できる
数列の漸化式が線形漸化式である場合は、高速きたまさ法が適用できる場合がある
- 線形漸化式：x[i]がそれ以前のK要素の線形計算によって求まる漸化式
- 線形漸化式のときは、行列累乗によるDP高速化が使える
- だが、場合によってはより制約が厳しい場合があり、その場合はきたまさ法か高速きたまさ法でないと通らない
  - この方法は多項式の線形漸化式での高速化手法である
  - 資料1 資料2 資料3 資料4
写像12相と母関数は相性がいい
- 分割数といえば形式的べき級数
  - maspy先生
  - 取っ掛かりとしては、を読むのも良いかもしれない
  - DPで計算するとO(N²)であるが、多項式でやるとO(NlogN)でできる
  - 特殊な漸化式が存在する、オイラーの五角数定理を使用する
    - 「x^k(3k+1)/2とx^k(3k-1)/2の係数がkが偶数なら-1で奇数なら1である形式的べき級数」を遷移で使う
    - これの32ページの下らへんにオイラーの五角数定理が書いてある
    - 実はこれの逆元がまんま、分割数の母関数 wikiに書いてある
- カタラン数
  - 高校数学の美しい物語で紹介されている
  - 母関数の閉じた形があるから、それを計算すればいい
  - 結城先生の無料で読める小説
- これも参考になりそう？
- 写像12相ではないけれど、ベルヌーイ数も高速に求められるっぽい(yosupoさんジャッジにあった)
  - ベルヌーイ数もあるってことは、スターリング数とかにもある？（要出典）

問題

母関数、形式的べき級数
線形漸化式、高速きたまさ法
- TDPC フィボナッチ
- ABC009 漸化式（行列累乗でも解ける）
Kinoshita-Li合成
- AC387 Prime Circuit