Yukicoder 980 Fibonacci Convolution Hard

問題の概要

数列 $\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)$
正整数 $q_{i} (i=1,2,..,Q)$ に対し、 $\displaystyle \sum_{s+t=q_{i}, s,t \ge 1} a_{s}⋅a_{t}$ を $10^{9}+7$ で割った余りを求めよ。

制約

$1 \le p \le 10^{9}$
$1 \le Q \le 2⋅10^{5}$
$2 \le q_{i} \le 2⋅10^{6}$

解法

この問題では $q_{i}$ が $Q$ 個与えられますが、 $q_{i}$ のとりうる値の個数と $Q$ とではオーダーがあまり変わらないので、とりうる値全てについて答を求めることにします。つまり、 $N=2⋅10^{6}$ に対して、 $N$ 以下の $q$ 全てに対して答を求めます。

f:id:tarattata1:20200213121747p:plain

上図の青枠で囲ったような部分の和 $S_{i}$ を全て求めるという問題になりますが、愚直にやると $O(N^{2})$ かかるので、何か工夫が必要です。このようなとき、１つの方法としては、 $S_{2}, S_{3}, S_{4},..$ というように順に求めていきながら、少し前（１つ前とか）の結果を使って簡単に $S_{i}$ が計算できると嬉しいです。そこで、数列の漸化式を見て、うまくやれるか考えてみましょう。

数列の漸化式 $a_{n} = p⋅a_{n−1} + a_{n-2}$ を以下のように書いてみます。

$(A,B,C)$ に関する条件 $P$ ：「 $A+p⋅B＝C$ 」
を考えたとき、 $(a_{n-2}, a_{n-1}, a_{n})$ は条件を満たす

すると、条件 $P$ は、
① $(A,B,C)$ が条件を満たすとき、定数倍した $(rA, rB, rC)$ も条件を満たす
② $(A_{1},B_{1},C_{1})$ と $(A_{2},B_{2},C_{2})$ が条件を満たすとき、 $(A_{1}+A_{2}, B_{1}+B_{2},　C_{1}+C_{2})$ も条件を満たす
という性質があります。（線形性）

f:id:tarattata1:20200213121805p:plain

さて、上図の各赤丸部分が条件 $P$ を満たすので、それらの和をとると、
$(S_{7},　S_{8}-a_{1}⋅a_{7},　S_{9}-a_{1}⋅a_{8}-a_{2}⋅a_{7}）$
も条件 $P$ を満たします。
よって、 $a_{1}=0, a_{2}=1$ を使うと、 $S_{9}=p⋅S_{8}+S_{7}+a_{7}$ とわかります。
同様にして、
$S_{n}=p⋅S_{n-1}+S_{n-2}+a_{n-2}$ $(n \ge 3)$
とわかるので、順に $S_{i}$ を求めることができます。