形式的べき級数

• 多項式を無限個の項を持つことができるように拡張したもの
  • 無限個の数列と対応する
    • $F={\sum }_{i=0}^{\infty }{f}_i{x}^i$
    • この時、形式的べき級数$F$ は数列 $\{f_i\}$の母関数という
  • 形式的べき級数Fからn次の項の係数を取り出す演算を$[x^n]F$と書く
• 多項式から引き継いだ都合の良い性質がある
  • 加算・減算
  • 乗算
    • $[x^n](F\times G)={\sum }_{i+j=n}([x^i]F\times [x^j]G)$

多項式・形式的べき級数（２）式変形による解法の導出 | maspyのHP

• 形式的べき級数の逆元を使った無限和圧縮

• 因数分解の利用

  • Fが因数分解できることによってそれぞれに二項定理を使える
  • $F^T=(A+B{)}^T(C+D{)}^T=({\sum }_i(\genfrac{}{}{0ex}{}{T}{i})A^i{B}^{T-i})\times ({\sum }_j(\genfrac{}{}{0ex}{}{T}{j})C^j{D}^{T-j})$
  • 積と和の交換して
  • $F^T=({\sum }_{i,j}(\genfrac{}{}{0ex}{}{T}{i}\left)\right(\genfrac{}{}{0ex}{}{T}{j})A^i{B}^{T-i}{C}^j{D}^{T-j})$

• 累積和による dp 遷移の導出

• 戻すDPの導出

• 交換法則・繰り返し二乗法の適用