多項式
- 数列の問題とか、組み合わせ問題を多項式の係数に置いて解くテクがある
- はまやんはまやん自信作の解説 testestestさんのまとまった資料
- 母関数・形式的べき級数
- 母関数・形式的べき級数の問題の流れ
- 数列とかDPを母関数にする
- うまいこといじると、多項式計算できる形になる
- それを頑張って計算すると、求めたい数列とかDPになってる
- 多項式の計算
- 母関数とか形式的べき級数とかでコネコネすると多項式の計算に帰着できる
- その後の問題として多項式の計算をどう効率良くやるかという点が問題として残る
- rngさんの形式的べき級数での効率良く計算できるやつまとめ
- yosupoさんのverifyもすごく便利
- DPで計算したほうが早い系
- *(1-xn), /(1-xn)
- (1+x+x2+...+xn) = (1-xn+1)(1+x+x2+...) = (1-xn+1)/(1-x)
- (1-xn+1)はFFTでやるよりDPの方で計算したほうが早い
- /(1-x)は累積和と同じ計算になるので、累積和したほうが早い
- どちらもO(N)でできるので、実はこの計算はO(N)でできる
- → EDPC M Candies, ARC028 注文の多い高橋商店
- 多項式の累乗はFFTをして、各要素を累乗して、逆FFTをすれば実現できる
- 数列の漸化式が線形漸化式である場合は、高速きたまさ法が適用できる場合がある
- 写像12相と母関数は相性がいい
- 分割数といえば形式的べき級数
- maspy先生
- 取っ掛かりとしては、数学ガールを読むのも良いかもしれない
- DPで計算するとO(N2)であるが、多項式でやるとO(NlogN)でできる
- 特殊な漸化式が存在する、オイラーの五角数定理を使用する
- 「xk(3k+1)/2とxk(3k-1)/2の係数がkが偶数なら-1で奇数なら1である形式的べき級数」を遷移で使う
- これの32ページの下らへんにオイラーの五角数定理が書いてある
- 実はこれの逆元がまんま、分割数の母関数 wikiに書いてある
- カタラン数
- 高校数学の美しい物語で紹介されている
- 母関数の閉じた形があるから、それを計算すればいい
- 結城先生の無料で読める小説
- これも参考になりそう?
- 写像12相ではないけれど、ベルヌーイ数も高速に求められるっぽい(yosupoさんジャッジにあった)
- ベルヌーイ数もあるってことは、スターリング数とかにもある?(要出典)
- 分割数といえば形式的べき級数
問題
- 母関数、形式的べき級数
- HR Array Restoring 多項式の商
- yukicoder No.3046 yukicoderの過去問 多項式の商
- CF250 The Child and Binary Tree 多項式の商・多項式の平方根
- yosupo 分割数 多項式の逆元
- AC 第5回 ドワンゴからの挑戦状 本選 Parentheses Inversions 解説 多項式の微分、商
- EDPC M Candies
- ARC028 注文の多い高橋商店
- AtCoder Candy Retribution 解説
- AtCoder フィボナッチ数の総和 解説
- CF D2. Wrong Answer on test 233 (Hard Version) 多項式の累乗
- 線形漸化式、高速きたまさ法
- TDPC フィボナッチ
- ABC009 漸化式 (行列累乗でも解ける)