yukicoder No.980 Fibonacci Convolution Hard

• 問題
• AC

$C_q := a_1a_{q-1} + a_2a_{q-2} + ... +a_{q-1}a_1$とすると、漸化式は次のように書ける:

$$\begin{aligned} C_q & = a_1a_{q-1} + a_2a_{q-2} + ... + a_{q-2}a_2 +a_{q-1}a_1 \\ & = a_1(pa_{q-2} + a_{q-3}) + a_2(pa_{q-3} + a_{q-4}) + ... a_{q-2}(pa_1 + a_0)+ a_{q-1}a_1 \\ & = p(a_1a_{q-2} + ... + a_{q-2}a_1) + (a_1a_{q-3}+...+a_{q-3}a_1) + a_{q-2} \\ & = pC_{q-1}+C_{q-2} + a_{q-2} \end{aligned}$$

ただし$a_0 = 1$とする。