Yukicoder 978 Fibonacci Convolution Easy

問題の概要

数列 $\lbrace a_{n} \rbrace$ $(n \ge 1)$ を以下で定める。
$a_{1}=0$ , $a_{2}=1$ , $a_{n} = p⋅a_{n−1} + a_{n-2}$ $(n \ge 3)$
このとき $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{i} a_{i}⋅a_{j}$ を $10^{9}+7$ で割った余りを求めよ。

制約

$1 \le N \le 2000000$
$1 \le p \le 10^{9}$

解法

求める式は、以下のものです。

$a_{1}⋅a_{1}$
$+ a_{2}⋅a_{1} + a_{2}⋅a_{2}$
$+ a_{3}⋅a_{1} + a_{3}⋅a_{2} + a_{3}⋅a_{3}$
$+ …$
$+ a_{N}⋅a_{1} + a_{N}⋅a_{2} + a_{N}⋅a_{3} + ... + a_{N}⋅a_{N}$

これを以下のように書き換えます。

$a_{1} ⋅ (a_{1})$
$+ a_{2} ⋅ (a_{1} + a_{2})$
$+ a_{3} ⋅ (a_{1} + a_{2} + a_{3})$
$+ …$
$+ a_{N} ⋅ (a_{1} + a_{2} + a_{3} + ... + a_{N})$

最初に各 $a_{i}$ を求めた後、 $(a_{1}), (a_{1} + a_{2}) , ... , (a_{1} + a_{2} + a_{3} +... + a_{N})$ という部分は順に $O(N)$ で計算できるので、全体でも $O(N)$ で計算できます。

他の解法

$\frac{(a_{1} + a_{2} + a_{3} +... + a_{N})^{2} - (a_{1}^{2} + a_{2}^{2} + a_{3}^{2} +... + a_{N}^{2})}{2}$ でも計算できます。
この式変形は、ときどき見ますね。（ここ半年で競プロで3回くらい見ました）