No.980 Fibonacci Convolution Hard

$ (a_i) の母関数が$ f(x):=\frac{x^2}{1-px-x^2} だから

$ b_i:=\sum_{j=0}^i a_{j}a_{i-j}で定義される$ (b_i) の母関数は

$ g(x):=f(x)^2=\frac{x^4}{(1-px-x^2)^2}=\frac{x^4}{1-2 p x + (p^2-2) x^2 + 2 p x^3+x^4}

となる。従って、

$ b_{i}=2pb_{i-1}+(2-p^2)b_{i-2}-2pb_{i-3}-b_{i-4}

$ b_0=b_1=b_2=b_3=0, b_4=1

から計算すればよい。