かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

TDPC T - フィボナッチ

典型 形式的冪級数 競技プログラミング 解説

問題はこちら

問題概要

少し変えてます．

  • {a_0=a_1=\dots =a_{K-1}=1}
  • {a_i=a_{i-1}+\dots +a_{i-K}(i\geq K)}

で定義される数列{a}の第{N}項{a_{N-1}}を求めよ．

{2\leq K\leq 1000\\ 1\leq N\leq 10^9}

解説

{a}の母関数を{f}とする．{f}は形式的冪級数{P}を用いて{\displaystyle f=\frac{P}{1-x-x^2\dots -x^K}}と表される．
{[x^i]P=[x^i]f-[x^{i-1}]f-[x^{i-2}]f\dots -[x^{i-K}]f}なので，
{i\geq K}のときは{[x^i]P=0}
{i < K}のときは{[x^i]P=[x^i]f-\sum_{j=0}^{i-1}[x^j]f=1-i}

したがってBostan–Moriのアルゴリズムを用いると{O(K\log{K}\log{N})}で解けた．

提出プログラム

https://atcoder.jp/contests/tdpc/submissions/27322572

感想

形式的冪級数の典型