Kth term of Linearly Recurrent Sequence

問題

judge.yosupo.jp

動機

Bostan-Mori のアルゴリズムで $\displaystyle \lbrack x ^ N \rbrack \dfrac{P}{Q}$ を高速に計算できると知っていても Kth term of Linearly Recurrent Sequence を解くにはややギャップがあると思ったので、書きました。新規性は何もありません。

解法

当然ですが、$\displaystyle P(x) := \sum _ {i = 0} ^ \infty a _ i \cdot x ^ i$ とすれば $\lbrack x ^ N\rbrack P$ が答えです。入力からは $a _ 0, \ldots, a _ {d - 1}$ しか分からないので、$\displaystyle Q(x) := 1 - \sum _ {i = 1} ^ d c _ i \cdot x ^ i$ と定義して式 $(1)$ を用いて計算します。

$$\lbrack x ^ N\rbrack P = \lbrack x ^ N \rbrack\dfrac{P\cdot Q}{Q} \tag{1}$$

ここで、$P\cdot Q$ に対して次の補題が成り立ちます。

補題

$n \geq d$ なる任意の整数 $n$ に対して、$\lbrack x ^ n\rbrack P\cdot Q = 0$ が成り立つ。

補題の証明

$n \geq d$ なる整数 $n$ を任意に固定する。$\lbrack x ^ n\rbrack P \cdot Q$ を定義通りに計算することで次を得る。 $$\lbrack x ^ n\rbrack P \cdot Q = a _ n - \sum _ {i = 1} ^ d c _ i a _ {n - i}.$$ $a$ の定義より $i \geq d$ なる整数 $i$ に対して $\displaystyle a _ i = \sum _ {j = 1} ^ d c _ j a _ {n - j}$ が成り立つので、これを $i = n\geq d$ として適用することで $\lbrack x ^ n\rbrack P \cdot Q = 0$ が従う。$\blacksquare$

補題より $P\cdot Q = (P\cdot Q) \bmod x ^ d = ((P\bmod x ^ d)\cdot Q)\bmod x ^ d$ として計算できます。$P\bmod x ^ d$ および $Q$ は入力から直ちに求まり、$P\cdot Q$ を $\Theta(d \log d)$ 時間で得ることができます。あとは Bostan-Mori のアルゴリズムを適用することで、全体 $\Theta(d\log d \log N)$ 時間で問題を解くことができます。