yukicoder No.980 Fibonacci Convolution Hard

No.980 Fibonacci Convolution Hard - yukicoder

変な解き方をしました…。後述するように厳密に正しい解法ではないので、あまりオススメはしません。

解法

0-indexedのほうが楽なので、数列 $a$ を $a_{0} = 0, a_{1} = 1,$ あとは同様の漸化式で定義される数列、としておきます。クエリで与えられた $q$ に対しては $2$ を引いて $s, t$ を非負整数とすれば同等の問題になります。

普通のフィボナッチ数列と同様、特性方程式 $x^{2} - px - 1 = 0$ の解を用いることで一般項を表現することができます。

$\alpha = \frac{p+\sqrt{p^{2}+4}}{2}$ とする。
$\beta = \frac{p-\sqrt{p^{2}+4}}{2}$ とする。
一般項は、 $a_{n} = \frac{1}{\sqrt{p^{2}+4}}(\alpha^{n} - \beta^{n})$ と表現できる。

これを踏まえてクエリで $q$ が与えられた時の答えを求めます。先述の通り、この $q$ は入力から $2$ 引いたものとします。答えは以下のように計算できます。

$\displaystyle\frac{1}{p^{2}+4}\left((\alpha^{0}-\beta^{0})(\alpha^{q}-\beta^{q}) + (\alpha^{1}-\beta^{1})(\alpha^{q-1}-\beta^{q-1}) + \cdots + (\alpha^{q}-\beta^{q})(\alpha^{0}-\beta^{0})\right)$

$\displaystyle =\frac{1}{p^{2}+4}\left((q+1)( \alpha^{q} + \beta^{q}) -2(\alpha^{0}\beta^{q} + \alpha^{1}\beta^{q-1} + \cdots + \alpha^{q}\beta^{0})\right)$

ここで $(\alpha^{0}\beta^{q} + \alpha^{1}\beta^{q-1} + \cdots + \alpha^{q}\beta^{0})$ は等比数列の和の公式を用いてあげることで

$\displaystyle\frac{\alpha^{q+1} - \beta^{q+1}}{\alpha - \beta}$

と等しいことが分かります。よって答えは以下のように表現できます。

$\displaystyle\frac{1}{p^{2}+4}\left( (q+1)( \alpha^{q} + \beta^{q}) -2\frac{\alpha^{q+1} - \beta^{q+1}}{\alpha - \beta}\right)$

ただ $\alpha, \beta$ には根号が含まれているのでそのまま $\bmod$ ありの計算をすることはできません。一般項を利用して、なんとかこれらの値を表現できないか考えます。

まず $\alpha^{q} + \beta^{q} = \frac{\alpha^{2q} + \beta^{2q}}{\alpha^{q}-\beta^{q}}$ であることから、これは $\frac{a_{2q}}{a_{q}}$ と等しくなります。

同様に $\frac{\alpha^{q+1} - \beta^{q+1}}{\alpha - \beta}$ は、 $\frac{a_{q+1}}{a_{1}} = a_{q+1}$ と等しくなります。

これで $\alpha, \beta$ を消去できました。答えは以下の式で求められます。

$\displaystyle\frac{1}{p^{2}+4}\left( (q+1)\frac{a_{2q}}{a_{q}} -2a_{q+1}\right)$

必要な範囲全ての $a_{n}$ を前計算しておいて、各クエリに対してこの式を用いて答えを計算することで、ACすることはできました。

…が、本当は $0$ 除算が発生し得ることに注意する必要があります。 $p^{2}+4 \equiv 0$ である場合は $\alpha^{q}$ や $\beta^{q}$ が簡単な式で表現できるようになるので比較的対処しやすいですが、 $q=0$ 以外で $a_{q} \equiv 0$ であるような場合は厄介だと思います…。